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.

Link to solution →

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.

Link to solution →

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.

Link to solution →

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.

Link to solution →

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.

Link to solution →

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



Tagged: #leetcode, #algorithm