Binary Trees and Binary Search Trees Questions

Focuses on tree data structures, specifically binary trees and binary search trees. Candidates should understand node relationships, common traversals including in order, pre order, post order, and level order, and be able to implement traversals both recursively and iteratively. Cover binary search tree properties and operations including search, insertion, deletion, validation of binary search tree property, and finding the lowest common ancestor. Include problems on tree paths, height and balance calculations, serialization and deserialization, checking and restoring balance at a high level, and use cases in system design. Emphasize complexity analysis, recursion versus iterative solutions using stacks or queues, and handling edge cases such as duplicate keys and degenerate trees.

EasyTechnical

49 practiced

Implement a search function for a BST in Python that returns the node or value if it exists and indicates failure otherwise. Explain how the BST property lets you avoid visiting the entire tree, and discuss the worst-case runtime on a skewed tree.

Sample Answer

A BST search follows the ordering rule, so I only move left or right instead of scanning the whole tree.

python

def bst_search(root, target):
    current = root
    while current:
        if current.val == target:
            return current
        elif target < current.val:
            current = current.left
        else:
            current = current.right
    return None

If the value exists, this returns the node; otherwise it returns `None`. The BST property lets me cut the search space in half at each step, so average time is O(log n) in a balanced tree. On a skewed tree, worst-case runtime becomes O(n), which is the same as a linked list. That matters in backend services because unbalanced data can create latency spikes under load.

MediumTechnical

53 practiced

Given two values in a BST, find their lowest common ancestor in Python. Explain the logic that lets you stop early without exploring the whole tree, and describe what happens if one of the values is not present.

Sample Answer

In a BST, I can stop early because every node splits the search space using the ordering property. If both values are smaller than the current node, the LCA must be in the left subtree; if both are larger, it must be in the right subtree. The first node where the values diverge is the answer.

python

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        a, b = p, q
        if a > b:
            a, b = b, a

        node = root
        while node:
            if b < node.val:
                node = node.left
            elif a > node.val:
                node = node.right
            else:
                return node
        return None

**Logic**- Both targets smaller → move left- Both targets larger → move right- Otherwise, current node is the split point and thus the LCA

**If one value is missing**- This version returns the split node only if the values would exist in the BST path- In a production setting, I’d first verify both values exist with a search, or make the function return `None` if either lookup fails

**Complexity**- Time: O(h)- Space: O(1)

This is much better than traversing the full tree when the BST property holds.

MediumTechnical

44 practiced

Implement iterative inorder traversal in Python using an explicit stack instead of recursion. Your answer should return the values in sorted order for a BST, and you should explain how the algorithm simulates the call stack and why it helps with deep trees.

Sample Answer

To do iterative inorder traversal, I use an explicit stack to simulate the recursion stack. The idea is to keep walking left, pushing nodes as I go, then pop the last node, visit it, and move to its right child.

python

def inorder_traversal(root):
    result = []
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        result.append(current.val)
        current = current.right

    return result

This is especially useful for deep trees because it avoids Python recursion depth limits. For a BST, the output is sorted because inorder visits nodes in ascending order.

Time: O(n)Space: O(h), where h is tree height.

MediumTechnical

46 practiced

Write Python code to delete a node from a BST and correctly handle all three cases: leaf node, node with one child, and node with two children. Explain how you choose the replacement node in the two-child case and how you keep the BST property intact.

Sample Answer

To delete from a BST, I’d recurse until I find the node, then handle the three structural cases separately.

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def deleteNode(self, root, key):
        if not root:
            return None

        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            if not root.left:
                return root.right
            if not root.right:
                return root.left

            # Two children: replace with inorder successor
            succ = root.right
            while succ.left:
                succ = succ.left
            root.val = succ.val
            root.right = self.deleteNode(root.right, succ.val)

        return root

**Cases**- **Leaf:** return `None`- **One child:** return that child directly- **Two children:** replace with inorder successor (smallest value in right subtree)

**Why successor works**It preserves the BST ordering: everything in the left subtree stays smaller, and everything in the right subtree stays larger.

**Complexity**- Time: O(h)- Space: O(h) recursion depth

In backend systems, I’d also consider rebalancing if this tree is part of a long-lived in-memory index, because repeated deletes can make the tree skewed.

MediumTechnical

43 practiced

Implement binary tree serialization and deserialization in Python so that any tree can be round-tripped exactly, including null children and unbalanced shapes. Describe the representation you would choose, how you would encode missing nodes, and how you would verify correctness.

Sample Answer

I’d serialize the tree in preorder and include an explicit null marker for missing children. That preserves exact shape, including skewed trees and internal gaps, which is important for round-tripping backend data structures.

**Approach**- Use `#` (or `None`) for nulls- Visit node, then left, then right- During deserialization, consume tokens in the same order

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    def serialize(self, root):
        vals = []
        def dfs(node):
            if not node:
                vals.append('#')
                return
            vals.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ','.join(vals)

    def deserialize(self, data):
        vals = iter(data.split(','))
        def dfs():
            v = next(vals)
            if v == '#':
                return None
            node = TreeNode(int(v))
            node.left = dfs()
            node.right = dfs()
            return node
        return dfs()

**Correctness check**- Serialize → deserialize → serialize should match exactly- Compare structure and values, not just node count

**Complexity**- Time: O(n)- Space: O(n) for output and recursion stack

**Edge cases**- Empty tree- Single node- Deeply unbalanced tree- Negative values and duplicates

Unlock Full Question Bank

Get access to hundreds of Binary Trees and Binary Search Trees interview questions and detailed answers.

Join thousands of developers preparing for their dream job.