Q: Validate BST. A solution checks node.left.val < node.val < node.right.val at each node. Which tree breaks it?

5 with left 4 and right 6, where 6 has left child 3 Every local check passes but 3 sits in the right subtree of 5, violating the BST property. Pass lower and upper bounds down instead. The plain 5, 4, 6 tree is a valid BST and passes. A single node and an empty tree are valid.

Q: Recursive max depth of a binary tree with n nodes. What is the worst case space?

O(n) for a skewed tree Recursion depth equals tree height, which is n for a linked list shaped tree. O(log n) holds only when balanced. Recursion is not O(1). No extra log factor applies.

Q: Diameter of Binary Tree: longest path between any two nodes, in edges. The helper returns height. What updates the answer at each node?

best = max(best, left_height + right_height) The longest path through a node joins the two deepest branches. 1 + max is the height, not a path. Only checking the root misses paths that do not pass through it. Multiplying heights has no meaning.

Q: Lowest Common Ancestor in a BST for p and q. Best time for a tree of height h?

O(h), walk down using values BST order says go left if both are smaller, right if both are larger, else stop. That is O(h). Comparing full paths is for general trees. O(log n) assumes balance. Nothing is sorted.

Q: Kth Smallest Element in a BST, k much smaller than n. You want to stop as soon as the kth value is found. Which traversal visits values in sorted order so you can stop at the kth visit?

Inorder Inorder visits left, node, right, which is ascending in a BST, so stop at the kth visit. Preorder and postorder do not sort. Level order visits by depth.

Q: Same Tree (check whether two binary trees match in shape and values): give the recursive check and its base cases.

If both are None return True. If one is None or values differ return False. Otherwise return same(p.left, q.left) and same(p.right, q.right). O(n) time, O(h) stack.

Question 1

Binary tree level order traversal with a deque. How do you separate levels?

Accepted Answer

Record len(queue) at the start of each level and pop exactly that many The queue length at the start of a level equals that level's node count. A None after every node splits per node, not per level. A stack gives DFS order. Incrementing per pop counts nodes, not levels.

Question 2

Validate BST. A solution checks node.left.val < node.val < node.right.val at each node. Which tree breaks it?

Accepted Answer

5 with left 4 and right 6, where 6 has left child 3 Every local check passes but 3 sits in the right subtree of 5, violating the BST property. Pass lower and upper bounds down instead. The plain 5, 4, 6 tree is a valid BST and passes. A single node and an empty tree are valid.

Question 3

Recursive max depth of a binary tree with n nodes. What is the worst case space?

Accepted Answer

O(n) for a skewed tree Recursion depth equals tree height, which is n for a linked list shaped tree. O(log n) holds only when balanced. Recursion is not O(1). No extra log factor applies.

Question 4

Diameter of Binary Tree: longest path between any two nodes, in edges. The helper returns height. What updates the answer at each node?

Accepted Answer

best = max(best, left_height + right_height) The longest path through a node joins the two deepest branches. 1 + max is the height, not a path. Only checking the root misses paths that do not pass through it. Multiplying heights has no meaning.

Question 5

Lowest Common Ancestor in a BST for p and q. Best time for a tree of height h?

Accepted Answer

O(h), walk down using values BST order says go left if both are smaller, right if both are larger, else stop. That is O(h). Comparing full paths is for general trees. O(log n) assumes balance. Nothing is sorted.

Question 6

Kth Smallest Element in a BST, k much smaller than n. You want to stop as soon as the kth value is found. Which traversal visits values in sorted order so you can stop at the kth visit?

Accepted Answer

Inorder Inorder visits left, node, right, which is ascending in a BST, so stop at the kth visit. Preorder and postorder do not sort. Level order visits by depth.

Question 7

Same Tree (check whether two binary trees match in shape and values): give the recursive check and its base cases.

Accepted Answer

If both are None return True. If one is None or values differ return False. Otherwise return same(p.left, q.left) and same(p.right, q.right). O(n) time, O(h) stack.

Tree coding interview questions

More coding topics

Practise these on your commute