# LeetCode's Binary tree

Validate binary search tree, Maximum depth of binary tree, Minimum depth of binary tree, Balanced binary tree, Binary tree maximum path sum

### 1. Given a binary tree, determine if it is a valid binary search tree.

Approach:

```
- Traverse the tree and apply recursion to check at each step if:
- the current node's value is greater than the lower bound
- the current node's value is smaller than the upper bound
- the current node's left child follows
- the current node's left child follows
```

Cost:

```
- O(n) time and O(n) stack space.
```

### 2. Given a binary tree, find its maximum depth.

Approach:

```
- The maximum depth of the current node is the greater of the max height of the left
subtree and the right subtree plus one.
```

Cost:

```
- O(n) time, O(n) space.
```

### 3. Given a binary tree, find its minimum depth.

Approach:

```
- Similar to finding maximum depth, the minimum depth of the current node is
the smaller of the min height of the left subtree and the right subtree plus one.
```

Cost:

```
- O(n) time, O(1) space where n is the length of a linked list.
```

### 4. Given a binary tree, determine if it is height-balanced.

Approach:

```
- Calculate max depth for the left subtree and right subtree.
- If either the left subtree or right subtree is unbalanced, return right away.
```

Cost:

```
- O(n) time, O(n) stack space.
```

### 5. Given a binary tree, find the maximum path sum.

Assumption:

```
- The path might start and end at any node in the tree.
- Assume the tree is non-empty.
- The node can contain negative number.
- The maximum path does not have to go though the root node.
```

Approach:

```
- At each node, the potential maximum path could be one of these cases:
- max(left subtree) + node
- max(right subtree) + node
- max(left subtree) + max(right subtree) + node
- the node itself
```

Cost:

```
- O(n) time, O(n) space.
```

For more coding problems, please visit https://github.com/hoanhan101/algo.

Tagged: #leetcode, #algorithm