# Week 6: Binary Trees

### Intro: Binary Tree Data Structure

A binary tree is a tree data structure in which each node can have at most two children, which are referred to as the left child and the right child.

The topmost node in a binary tree is called the root, and the bottom-most nodes are called leaves.

A binary tree can be visualized as a hierarchical structure with the root at the top and the leaves at the bottom.

Each node in the tree contains the following:

- Data
- Pointer to the left child
- Pointer to the right child

```
1
/ \
2 3
/ \
4 5
```

**Example of tree node with integer data (Java)**

```
// Class containing a node with a left and right child and some data
class Node {
int data;
Node left, right;
public Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
```

### 1) Maximum Depth of Binary Tree

Given the `root`

of a binary tree, return its **maximum depth**.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

**Example 1:**

```
Input: 3
/ \
9 20
/ \
15 7
Output: 3
```

**Example 2:**

```
Input: 1
\
2
Output: 2
```

*Constraints:*

- The number of nodes in the tree is in the range
`[0, 104]`

. `-100 <= Node.val <= 100`

### 2) Evaluate Boolean Binary Tree

You are given the `root`

of a **full binary tree** with the following properties:

**Leaf nodes**have either the value`0`

or`1`

, where`0`

represents`False`

and`1`

represents`True`

.**Non-leaf nodes**have either the value`2`

or`3`

, where`2`

represents the boolean`OR`

and`3`

represents the boolean`AND`

.

The evaluation of a `node`

is as follows:

- If the node is a leaf node, the evaluation is the
**value**of the node, i.e.`True`

or`False`

. - Otherwise, evaluate the node’s two children and apply the boolean operation of its value with the children’s evaluations.

Return the boolean result of evaluating the `root`

node.

A **full binary tree** is a binary tree where each node has either `0`

or `2`

children.

A **leaf node** is a node that has zero children.

**Example 1:**

```
Input: 2 AKA: OR
/ \ / \
1 3 True AND
/ \ / \
0 1 False True
Output: true
Explanation:
The AND node evaluates to False AND True = False.
The OR node evaluates to True OR False = True.
The root node evaluates to True, so we return true.
```

**Example 2:**

```
Input: 0
Output: false
Explanation: The root node is a leaf node and it evaluates to false, so we return false.
```

*Constraints:*

- The number of nodes in the tree is in the range
`[1, 1000]`

. `0 <= Node.val <= 3`

- Every node has either
`0`

or`2`

children. - Leaf nodes have a value of
`0`

or`1`

. - Non-leaf nodes have a value of
`2`

or`3`

.

### 3) Same Tree

Given the roots of two binary trees `p`

and `q`

, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

**Example 1:**

```
Input: p q
1 1
/ \ / \
2 3 2 3
Output: true
```

**Example 2:**

```
Input: p q
1 1
/ \ / \
2 1 1 2
Output: false
```

*Constraints:*

- The number of nodes in both trees is in the range
`[0, 100]`

. `-10^4 <= Node.val <= 10^4`

### 4) Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes `p`

and `q`

as the lowest node in `T`

that has both `p`

and `q`

as descendants (where we allow a node to be a descendant of itself).”

**Example 1:**

```
Input: 3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
```

**Example 2:**

```
Input: 3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
```

*Constraints:*

- The number of nodes in the tree is in the range
`[2, 10^5]`

. `-10^9 <= Node.val <= 10^9`

- All
`Node.val`

are unique. `p != q`

`p`

and`q`

will exist in the tree.