Tree Data Structure Interview Questions

Tree Interview Questions

Trees are one of the most important topics in data structures and coding interviews. Tree questions test your understanding of hierarchical data, recursion, traversal, node relationships, and tree properties.

Common interview problems include traversing binary trees, finding their height, checking whether they are balanced, validating binary search trees, finding the lowest common ancestor, and constructing trees from traversal sequences.

1. What Is a Tree Data Structure?

A tree is a non-linear data structure that represents hierarchical relationships using nodes connected by edges.

        A
       / \
      B   C
     / \
    D   E

The top node is called the root. Nodes below another node are its children, while the node directly above them is their parent.

2. What Is a Binary Tree?

A binary tree is a tree in which each node has at most two children. These children are commonly called the left child and right child.

        10
       /  \
      5    15
     / \
    2   7

A binary tree does not require its values to be sorted. That property belongs to a binary search tree.

3. What Is the Difference Between a Binary Tree and a Binary Search Tree?

A binary tree only limits each node to at most two children. A binary search tree (BST) additionally maintains an ordering rule.

BST:

        10
       /  \
      5    15
     / \
    2   7

Left subtree  <  10
Right subtree >  10

This ordering allows efficient searching when the tree remains reasonably balanced.

4. What Are the Important Tree Terms?

Some terminology appears repeatedly in tree interview questions.

5. What Are the Main Types of Binary Trees?

• Full binary tree: every node has either zero or two children.
• Complete binary tree: every level is full except possibly the last, which is filled from left to right.
• Perfect binary tree: every internal node has two children and all leaves are at the same level.
• Balanced binary tree: the height is kept reasonably small relative to the number of nodes.
• Degenerate tree: each node has at most one child, making the structure resemble a linked list.

6. How Do You Define a Tree Node?

A binary tree node normally stores a value and references to its left and right children.

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

7. What Are the Three Depth-First Tree Traversals?

The three common depth-first traversals are preorder, inorder, and postorder.

        A
       / \
      B   C
     / \
    D   E

Preorder:
A → B → D → E → C

Inorder:
D → B → E → A → C

Postorder:
D → E → B → C → A

8. What Is Preorder Traversal?

Preorder visits nodes in this order: Root → Left → Right.

function preorder(root) {
  if (root === null) {
    return;
  }

  console.log(root.value);

  preorder(root.left);
  preorder(root.right);
}

Preorder is useful when the root needs to be processed before its descendants and is also useful when serializing or reconstructing certain tree structures.

9. What Is Inorder Traversal?

Inorder visits nodes in this order: Left → Root → Right.

function inorder(root) {
  if (root === null) {
    return;
  }

  inorder(root.left);

  console.log(root.value);

  inorder(root.right);
}

An important interview fact is that inorder traversal of a valid binary search tree produces values in sorted order, assuming the tree's ordering convention is followed.

10. What Is Postorder Traversal?

Postorder visits nodes in this order: Left → Right → Root.

function postorder(root) {
  if (root === null) {
    return;
  }

  postorder(root.left);
  postorder(root.right);

  console.log(root.value);
}

Postorder is useful when child subtrees need to be processed before their parent, such as deleting or evaluating expression trees.

11. What Is Level-Order Traversal?

Level-order traversal visits nodes one level at a time from top to bottom. It is commonly implemented using a queue.

        1
       / \
      2   3
     / \
    4   5

Level order:

1 → 2 → 3 → 4 → 5

12. How Do You Implement Level-Order Traversal?

function levelOrder(root) {
  if (root === null) {
    return [];
  }

  const queue = [root];
  const result = [];
  let front = 0;

  while (front < queue.length) {
    const node = queue[front++];

    result.push(node.value);

    if (node.left !== null) {
      queue.push(node.left);
    }

    if (node.right !== null) {
      queue.push(node.right);
    }
  }

  return result;
}

Every node is processed once, giving O(n) time complexity. The queue can require O(n) auxiliary space in the worst case.

13. How Do You Find the Height of a Binary Tree?

The height can be calculated recursively as one plus the maximum height of the left and right subtrees. The exact base value depends on whether height is measured in edges or nodes.

function height(root) {
  if (root === null) {
    return 0;
  }

  return 1 + Math.max(
    height(root.left),
    height(root.right)
  );
}

With this definition, an empty tree has height 0 and a single-node tree has height 1.

14. What Is the Difference Between Height and Depth?

Depth measures how far a node is from the root. Height measures the longest downward path from a node to a leaf.

        A
       /
      B
     /
    C

Depth of C:
2 edges from A

Height of A:
2 edges to C

Height of C:
0 edges

15. How Do You Count the Number of Nodes in a Binary Tree?

function countNodes(root) {
  if (root === null) {
    return 0;
  }

  return (
    1 +
    countNodes(root.left) +
    countNodes(root.right)
  );
}

Each node is visited once, so the time complexity is O(n).

16. How Do You Count Leaf Nodes?

A leaf is a node with no left or right child.

function countLeaves(root) {
  if (root === null) {
    return 0;
  }

  if (
    root.left === null &&
    root.right === null
  ) {
    return 1;
  }

  return (
    countLeaves(root.left) +
    countLeaves(root.right)
  );
}

17. How Do You Find the Maximum Value in a Binary Tree?

In a general binary tree, there is no ordering guarantee. Therefore, all relevant nodes may need to be examined.

function findMaximum(root) {
  if (root === null) {
    return -Infinity;
  }

  return Math.max(
    root.value,
    findMaximum(root.left),
    findMaximum(root.right)
  );
}

The time complexity is O(n).

18. How Do You Search for a Value in a Binary Tree?

In a general binary tree, you cannot use value ordering to eliminate an entire subtree. DFS or BFS can be used to search the tree.

function contains(root, target) {
  if (root === null) {
    return false;
  }

  if (root.value === target) {
    return true;
  }

  return (
    contains(root.left, target) ||
    contains(root.right, target)
  );
}

19. How Do You Insert a Value into a Binary Search Tree?

In a BST, values smaller than the current node are normally placed in the left subtree, while larger values are placed in the right subtree. Duplicate handling depends on the chosen BST convention.

function insert(root, value) {
  if (root === null) {
    return new TreeNode(value);
  }

  if (value < root.value) {
    root.left = insert(root.left, value);
  } else if (value > root.value) {
    root.right = insert(root.right, value);
  }

  return root;
}

The average time is O(log n) for a balanced BST, while the worst case is O(n) when the tree becomes highly skewed.

20. How Do You Search in a Binary Search Tree?

function searchBST(root, target) {
  let current = root;

  while (current !== null) {
    if (current.value === target) {
      return current;
    }

    if (target < current.value) {
      current = current.left;
    } else {
      current = current.right;
    }
  }

  return null;
}

At each node, the BST ordering allows one subtree to be eliminated from consideration. The complexity is O(h), where h is the tree height.

21. What Is the Time Complexity of BST Search?

BST search is O(h), where h is the height of the tree.

Balanced BST:

        8
       / \
      4   12
     / \
    2   6

Height ≈ log n

Search ≈ O(log n)


Skewed BST:

8
   12
         20
               30

Height ≈ n

Search = O(n)

22. How Do You Validate a Binary Search Tree?

Checking only the immediate children is not enough. A valid BST must satisfy the ordering constraint throughout every subtree.

One reliable approach passes an allowed minimum and maximum range down the tree.

function isValidBST(root) {
  function validate(node, min, max) {
    if (node === null) {
      return true;
    }

    if (
      node.value <= min ||
      node.value >= max
    ) {
      return false;
    }

    return (
      validate(node.left, min, node.value) &&
      validate(node.right, node.value, max)
    );
  }

  return validate(
    root,
    -Infinity,
    Infinity
  );
}

23. How Do You Find the Minimum Value in a BST?

In a BST, the smallest value is located at the leftmost node.

function findMinimum(root) {
  if (root === null) {
    return null;
  }

  let current = root;

  while (current.left !== null) {
    current = current.left;
  }

  return current.value;
}

24. How Do You Find the Maximum Value in a BST?

The maximum value is located at the rightmost node.

function findMaximumBST(root) {
  if (root === null) {
    return null;
  }

  let current = root;

  while (current.right !== null) {
    current = current.right;
  }

  return current.value;
}

25. How Do You Delete a Node from a BST?

BST deletion has three main cases:

1. The node is a leaf.
2. The node has one child.
3. The node has two children.

For a node with two children, the node is commonly replaced by its inorder successor or inorder predecessor, followed by deletion of that replacement node.

function deleteBST(root, value) {
  if (root === null) {
    return null;
  }

  if (value < root.value) {
    root.left = deleteBST(
      root.left,
      value
    );
  } else if (value > root.value) {
    root.right = deleteBST(
      root.right,
      value
    );
  } else {
    if (root.left === null) {
      return root.right;
    }

    if (root.right === null) {
      return root.left;
    }

    let successor = root.right;

    while (successor.left !== null) {
      successor = successor.left;
    }

    root.value = successor.value;

    root.right = deleteBST(
      root.right,
      successor.value
    );
  }

  return root;
}

26. What Is the Lowest Common Ancestor?

The Lowest Common Ancestor (LCA) of two nodes is the deepest node that is an ancestor of both nodes.

        10
       /  \
      5    15
     / \
    2   7

LCA(2, 7) = 5
LCA(2, 15) = 10

27. How Do You Find the LCA in a Binary Search Tree?

The BST ordering property makes the problem simpler. If both target values are smaller than the current node, move left. If both are larger, move right. Otherwise, the current node is the split point and therefore the LCA.

function lowestCommonAncestor(
  root,
  first,
  second
) {
  let current = root;

  while (current !== null) {
    if (
      first < current.value &&
      second < current.value
    ) {
      current = current.left;
    } else if (
      first > current.value &&
      second > current.value
    ) {
      current = current.right;
    } else {
      return current;
    }
  }

  return null;
}

28. How Do You Find the LCA in a General Binary Tree?

A general binary tree does not provide BST ordering, so the algorithm must inspect the subtrees.

function lowestCommonAncestorBinaryTree(
  root,
  first,
  second
) {
  if (
    root === null ||
    root === first ||
    root === second
  ) {
    return root;
  }

  const left =
    lowestCommonAncestorBinaryTree(
      root.left,
      first,
      second
    );

  const right =
    lowestCommonAncestorBinaryTree(
      root.right,
      first,
      second
    );

  if (
    left !== null &&
    right !== null
  ) {
    return root;
  }

  return left !== null
    ? left
    : right;
}

29. How Do You Check Whether Two Binary Trees Are Identical?

Two binary trees are identical when their corresponding nodes have equal values and their structures are the same.

function areIdentical(first, second) {
  if (
    first === null &&
    second === null
  ) {
    return true;
  }

  if (
    first === null ||
    second === null
  ) {
    return false;
  }

  return (
    first.value === second.value &&
    areIdentical(
      first.left,
      second.left
    ) &&
    areIdentical(
      first.right,
      second.right
    )
  );
}

30. How Do You Check Whether One Tree Is a Subtree of Another?

A common approach is to traverse the larger tree and, whenever a matching value is found, compare the corresponding subtree structures.

A straightforward recursive solution can take O(nm) in the worst case, where n is the size of the main tree and m is the size of the candidate subtree.

31. How Do You Check Whether a Binary Tree Is Balanced?

A binary tree is height-balanced when the heights of the left and right subtrees of each node differ by no more than one, according to the standard definition.

A bottom-up recursive solution can calculate height while immediately reporting an imbalance.

function isBalanced(root) {
  function getHeight(node) {
    if (node === null) {
      return 0;
    }

    const leftHeight =
      getHeight(node.left);

    if (leftHeight === -1) {
      return -1;
    }

    const rightHeight =
      getHeight(node.right);

    if (rightHeight === -1) {
      return -1;
    }

    if (
      Math.abs(
        leftHeight - rightHeight
      ) > 1
    ) {
      return -1;
    }

    return 1 + Math.max(
      leftHeight,
      rightHeight
    );
  }

  return getHeight(root) !== -1;
}

This approach runs in O(n) time because each node is processed once.

32. What Is a Balanced Binary Search Tree?

A balanced BST keeps its height sufficiently small so that operations such as search, insertion, and deletion remain efficient.

AVL trees and Red-Black trees are examples of self-balancing binary search trees.

33. What Is a Complete Binary Tree?

A complete binary tree has every level completely filled except possibly the final level. The final level is filled from left to right.

Complete:

        1
       / \
      2   3
     / \
    4   5

Also complete:

        1
       / \
      2   3
     / \
    4   5
   /
  6

Heaps use complete binary trees because their shape allows efficient array representation.

34. What Is a Full Binary Tree?

In a full binary tree, every node has either zero children or exactly two children.

Full:

        1
       / \
      2   3
     / \
    4   5

Node 2 has two children and nodes 3, 4, and 5 are leaves.

35. What Is a Perfect Binary Tree?

A perfect binary tree has every internal node with exactly two children and all leaves at the same depth.

        1
       / \
      2   3
     / \ / \
    4  5 6  7

If the tree has height h measured in edges, a perfect binary tree contains 2^(h + 1) - 1 nodes.

36. How Do You Find the Diameter of a Binary Tree?

The diameter is the longest path between two nodes. Depending on the problem's definition, the answer may be measured in edges or nodes, so the convention should be clarified.

A common O(n) solution computes subtree heights while updating the largest path that passes through each node.

function diameter(root) {
  let longest = 0;

  function height(node) {
    if (node === null) {
      return 0;
    }

    const left = height(node.left);
    const right = height(node.right);

    longest = Math.max(
      longest,
      left + right
    );

    return 1 + Math.max(
      left,
      right
    );
  }

  height(root);

  return longest;
}

37. How Do You Find the Maximum Depth of a Binary Tree?

Maximum depth can be calculated recursively by taking one plus the larger depth of the two child subtrees.

function maxDepth(root) {
  if (root === null) {
    return 0;
  }

  return 1 + Math.max(
    maxDepth(root.left),
    maxDepth(root.right)
  );
}

38. How Do You Find the Minimum Depth of a Binary Tree?

Minimum depth is the number of nodes along the shortest path from the root to a leaf. A common mistake is to take the minimum of the two child depths without handling missing children correctly.

function minDepth(root) {
  if (root === null) {
    return 0;
  }

  if (
    root.left === null &&
    root.right === null
  ) {
    return 1;
  }

  if (root.left === null) {
    return 1 + minDepth(root.right);
  }

  if (root.right === null) {
    return 1 + minDepth(root.left);
  }

  return 1 + Math.min(
    minDepth(root.left),
    minDepth(root.right)
  );
}

39. How Do You Find the Kth Smallest Element in a BST?

Inorder traversal of a BST visits values in sorted order. Therefore, the kth visited node during inorder traversal is the kth smallest value.

function kthSmallest(root, k) {
  const stack = [];
  let current = root;

  while (
    current !== null ||
    stack.length > 0
  ) {
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    current = stack.pop();
    k--;

    if (k === 0) {
      return current.value;
    }

    current = current.right;
  }

  return null;
}

40. How Do You Find the Kth Largest Element in a BST?

The reverse of inorder traversal visits BST values in descending order: Right → Root → Left.

        8
       / \
      4   12
     / \   \
    2   6   15

Reverse inorder:

15 → 12 → 8 → 6 → 4 → 2

41. How Do You Build a Binary Tree from Preorder and Inorder Traversals?

Preorder identifies the root first. Inorder tells us which nodes belong to the left and right subtrees.

Preorder:
A B D E C

Inorder:
D B E A C

Root:
A

Left subtree:
D B E

Right subtree:
C

A hash map can store inorder positions so that each root can be located efficiently. The resulting algorithm can run in O(n) time when the map is used appropriately.

42. How Do You Serialize and Deserialize a Binary Tree?

Serialization converts a tree into a representation that can be stored or transmitted. Deserialization reconstructs the tree from that representation.

A preorder traversal with explicit null markers can preserve both node values and tree structure.

        1
       / \
      2   3

Serialized:

1,2,#,#,3,#,#

43. What Is a Skewed Binary Tree?

A skewed tree is one in which nodes predominantly have only one child. It can resemble a linked list.

10
  \
   20
     \
      30
        \
         40

A skewed BST has height O(n), causing search, insertion, and deletion to degrade to O(n).

44. Why Is Recursion Common in Tree Problems?

A tree is naturally recursive because every node can be viewed as the root of its own left and right subtrees.

Tree
├── Left subtree
│   ├── Left subtree
│   └── Right subtree
└── Right subtree
    ├── Left subtree
    └── Right subtree

This makes recursive definitions convenient for traversal, height calculation, searching, validation, and many divide-and-conquer tree problems.

45. What Is the Space Complexity of Recursive Tree Traversal?

Recursive DFS traversal uses the call stack. The auxiliary space is O(h), where h is the height of the tree.

For a balanced tree, h is approximately O(log n). For a skewed tree, h can become O(n).

46. How Do You Perform Iterative Inorder Traversal?

An explicit stack can simulate the call stack used by recursive inorder traversal.

function inorderIterative(root) {
  const stack = [];
  const result = [];
  let current = root;

  while (
    current !== null ||
    stack.length > 0
  ) {
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    current = stack.pop();

    result.push(current.value);

    current = current.right;
  }

  return result;
}

47. How Do You Compare DFS and BFS for Trees?

48. What Are the Most Important Tree Interview Patterns?

Tree questions become easier when you identify the underlying pattern before writing code.

49. How Should You Approach a Tree Interview Problem?

1. Identify whether the tree is binary, a BST, balanced, complete, or another type.
2. Clarify whether the problem asks for nodes, edges, height, or depth.
3. Draw a small tree before changing pointers or writing recursion.
4. Determine whether DFS or BFS better matches the problem.
5. For BST questions, actively use the ordering property.
6. For recursive problems, define what the function returns for one subtree.
7. Check empty trees and single-node trees.
8. Analyze the recursion depth or queue size for auxiliary space.

Common Tree Interview Mistakes

Confusing Binary Trees with BSTs

A binary tree does not automatically have sorted values. Only use BST ordering when the problem explicitly provides that property.

Using Minimum Height Logic Incorrectly

When calculating minimum depth, a missing child cannot simply be treated as height zero if the goal is to reach a leaf.

Ignoring the Definition of Height

Some problems measure height in edges while others measure it in nodes. State the convention before implementing the solution.

Using the Wrong Traversal

Inorder is particularly important for BSTs, while level-order naturally uses BFS. Choosing the traversal based on the problem can simplify the solution considerably.

Forgetting Skewed Trees

A recursive solution that uses O(h) space may require O(n) space when the tree is completely skewed.

Tree Interview Complexity Revision

Binary tree traversal     → O(n)
Search in binary tree     → O(n)

BST search                → O(h)
BST insertion             → O(h)
BST deletion              → O(h)

Balanced BST:
h ≈ log n
Operations ≈ O(log n)

Skewed BST:
h ≈ n
Operations = O(n)

DFS auxiliary space       → O(h)
BFS auxiliary space       → O(w)

where:
h = tree height
w = maximum tree width

Key Takeaways

• A tree represents hierarchical relationships between nodes.
• A binary tree allows at most two children per node.
• A BST adds an ordering property that enables directed searching.
• Preorder, inorder, postorder, and level-order are core tree traversals.
• Inorder traversal of a BST produces sorted values under the standard ordering convention.
• Tree recursion usually follows the structure of left and right subtrees.
• BST operations take O(h), where h is the tree height.
• A balanced BST can provide O(log n) height, while a skewed BST can degrade to O(n).
• Bottom-up recursion is useful for balance, diameter, and subtree calculations.
• BFS is useful for level-based tree problems and uses a queue.
• Always clarify whether height and depth are measured in nodes or edges.