# 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.
``````