Trees and Binary Search Trees Questions

Tree data structures as tested in coding interviews: binary trees, binary search trees, self-balancing trees (AVL insertion and deletion with rotations, a comparison with red-black trees, and alternatives such as treaps, splay trees and scapegoat trees), tries (prefix trees and radix trees), and N-ary, size-augmented and sum-augmented trees such as order-statistic trees. Covers traversal orders (in/pre/post-order, level-order, zigzag, iterative, generator-based and Morris variants), BST search, insertion and deletion invariants including duplicate-key policies, validation, successor and iterator design, range and kth-smallest queries, lowest common ancestor (including parent pointers, binary lifting and repeated queries on a static tree), tree reconstruction from traversals, serialization formats and parsing, converting between trees and sorted lists or linked lists, height, balance, diameter and path-sum recursion, subtree equality and hashing, persistent and snapshot-consistent trees, and how tree shape drives logarithmic versus degenerate performance. Excludes plain linked-list and stack/queue exercises with no tree in them, tree dynamic programming recurrences, general graph traversal, heap mechanics, and on-disk database index design, which are covered elsewhere.

EasyTechnical
60 practiced

What distinguishes a full, a perfect and a complete binary tree? For each, how would you check that a given tree has the property, and at what cost?

MediumTechnical
61 practiced

Given two BSTs, produce one sorted list of all their elements in O(m + n) time and O(h1 + h2) extra space. How would the same synchronized walk give the keys in one tree but not the other, or a merged balanced tree?

EasyTechnical
58 practiced

Compute the height of a binary tree, recursively and then iteratively with BFS. Say up front what you return for an empty tree and for a single node, and what the stack depth is on a skewed tree.

EasyTechnical
55 practiced

When would you choose a BST over a hash map or a sorted array? Compare lookup speed, insertion cost, ordered traversal and range queries, and memory.

EasyTechnical
61 practiced

How do binary-tree traversals relate to depth-first search on a graph? Show how DFS over a tree stored as adjacency lists yields preorder and postorder, and explain why inorder only makes sense for binary trees.

Unlock Full Question Bank

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

Sign in to Continue

Join thousands of developers preparing for their dream job.