Bird
Raised Fist0
Interview Preptree-dfseasyAmazonGoogleBloomberg

Balanced Binary Tree

Choose your preparation mode4 modes available
📋
Problem

Imagine you are designing a system that needs to keep data balanced for efficient retrieval, like a balanced family tree where no branch is too deep compared to others.

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is defined as a binary tree in which the left and right subtrees of every node differ in height by no more than 1. Input: The root node of a binary tree. Output: Return true if the tree is height-balanced, otherwise false.

1 ≤ n ≤ 10^5 (number of nodes)Node values can be any integerTree can be skewed or complete
Edge cases: Empty tree → true (an empty tree is balanced)Single node tree → true (only one node, balanced)Completely skewed tree (all nodes only on one side) → false
</>
IDE
def isBalanced(root: Optional[TreeNode]) -> bool:public boolean isBalanced(TreeNode root)bool isBalanced(TreeNode* root)function isBalanced(root)
def isBalanced(root):
    # Write your solution here
    pass
class Solution {
    public boolean isBalanced(TreeNode root) {
        // Write your solution here
        return false;
    }
}
#include <vector>
using namespace std;

bool isBalanced(TreeNode* root) {
    // Write your solution here
    return false;
}
function isBalanced(root) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: trueFailing to detect imbalance in skewed or deep subtree cases due to missing or incorrect height difference checks.✅ Add condition to return false immediately if abs(left_height - right_height) > 1 at any node.
Wrong: falseIncorrectly returning false for empty or single-node trees by not handling base cases.✅ Return true immediately if root is null or if node has no children.
Wrong: trueNot using early exit, causing incorrect results when imbalance is detected deep in the tree.✅ Implement early exit by returning a sentinel value (e.g., -1) to indicate imbalance and propagate it up.
Wrong: TLEUsing brute force approach that recomputes height for each node causing O(n^2) complexity.✅ Use a single postorder traversal that returns height and balance status simultaneously to achieve O(n).
✓
Test Cases
t1_01basic
Input{"root":[3,9,20,null,null,15,7]}
Expectedtrue

The left subtree height is 1, right subtree height is 2, difference is 1 which is allowed.

t1_02basic
Input{"root":[1,2,2,3,3,null,null,4,4]}
Expectedfalse

The left subtree is deeper by more than 1 level at node 2, so the tree is unbalanced.

t2_01edge
Input{"root":[]}
Expectedtrue

An empty tree is balanced by definition.

t2_02edge
Input{"root":[1]}
Expectedtrue

Single node tree is balanced as both subtrees are empty.

t2_03edge
Input{"root":[1,2,null,3,null,4,null,5]}
Expectedfalse

Completely skewed tree with nodes only on left side is unbalanced.

t3_01corner
Input{"root":[1,2,2,3,null,null,3,4,null,null,4]}
Expectedfalse

Tree where imbalance occurs deep in subtree; tests early exit correctness.

t3_02corner
Input{"root":[1,2,2,3,null,null,3,4,null,null,4,5]}
Expectedfalse

Tests confusion between 0/1 and unbounded recursion: extra nodes cause imbalance.

t3_03corner
Input{"root":[1,2,2,3,3,null,null,4,4,null,null,null,null,5]}
Expectedfalse

Greedy trap: assuming local balance implies global balance is incorrect.

t4_01performance
Input{"root":[1,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10]}
⏱ Performance - must finish in 2000ms

n=10 (skewed tree) tests O(n) complexity; brute force O(n^2) will time out for large n.

Practice

(1/5)
1. Given a binary tree, you need to find the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. Which approach guarantees an optimal solution to this problem?
easy
A. Perform a postorder traversal computing heights and update the diameter at each node using recursion with a global variable.
B. Apply dynamic programming with memoization on node pairs to find longest paths.
C. Use a greedy traversal that always chooses the deeper subtree at each node.
D. Calculate the height of the tree and multiply by two to estimate the diameter.

Solution

  1. Step 1: Understand the problem requires the longest path between any two nodes, not necessarily passing through root.

    The diameter can be found by checking the sum of left and right subtree heights at every node.
  2. Step 2: Recognize that a postorder traversal with recursion and a global variable to track diameter updates at each node ensures all paths are considered.

    This approach visits each node once, updating the diameter with left_height + right_height.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Postorder traversal with global diameter update covers all nodes [OK]
Hint: Diameter updates at every node, not just root [OK]
Common Mistakes:
  • Thinking diameter must pass through root
  • Using greedy to pick deeper subtree only
  • Confusing diameter with twice height
2. What is the space complexity of the optimal in-place flatten algorithm that uses reverse preorder traversal with a global pointer on a binary tree of n nodes and height h?
medium
A. O(n) due to storing all nodes in a list during traversal
B. O(1) because the algorithm modifies the tree in-place without extra memory
C. O(log n) because the tree height is always balanced and recursion stack is limited
D. O(h) due to recursion stack depth in worst case of skewed tree

Solution

  1. Step 1: Identify auxiliary space usage

    The algorithm uses recursion, so space is dominated by recursion stack depth, which is the tree height h.
  2. Step 2: Clarify why O(h) not O(1) or O(n)

    It does not store nodes externally (not O(n)) and is not constant space due to recursion stack (not O(1)). For skewed trees, h can be up to n.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Recursion stack space equals tree height h [OK]
Hint: Recursion stack space equals tree height h [OK]
Common Mistakes:
  • Assuming O(1) space because of in-place modification
  • Confusing recursion stack with explicit data structures
  • Assuming balanced tree always so O(log n) space
3. What is the time complexity of the BFS-based algorithm to compute the maximum depth of a binary tree with n nodes, and why might the following common misconception be incorrect? Options:
medium
A. O(n), but with O(n) auxiliary space for the queue at the widest level
B. O(n), because each node is visited exactly once in BFS
C. O(n log n), because each level requires sorting nodes
D. O(n^2), because each node is enqueued and dequeued multiple times

Solution

  1. Step 1: Identify time complexity

    BFS visits each node exactly once, so time complexity is O(n).
  2. Step 2: Identify space complexity and common misconception

    Queue can hold up to O(n) nodes at the widest level, so auxiliary space is O(n). The misconception is thinking nodes are processed multiple times, leading to O(n^2).
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Each node enqueued and dequeued once; max queue size O(n) [OK]
Hint: BFS visits each node once; space depends on max level width [OK]
Common Mistakes:
  • Assuming multiple visits per node
  • Confusing sorting with traversal
  • Ignoring queue space usage
4. Suppose you want to perform a preorder traversal on a binary tree where nodes can have parent pointers but no left or right pointers. Which approach correctly adapts preorder traversal to this scenario without extra space?
hard
A. Use a modified iterative approach that tracks previously visited nodes to avoid revisiting
B. Use recursion on parent pointers to simulate traversal
C. Iteratively traverse using parent pointers and a stack to track visited nodes
D. Use Morris traversal by creating temporary threaded links on parent pointers

Solution

  1. Step 1: Understand traversal constraints

    Without left/right pointers, standard Morris or recursion is not applicable; parent pointers only allow upward traversal.
  2. Step 2: Identify correct approach

    Tracking previously visited nodes iteratively allows preorder traversal by moving up/down without extra space for recursion stack.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Modified iterative approach handles parent-only trees without extra space [OK]
Hint: Parent-only trees require tracking visited nodes iteratively [OK]
Common Mistakes:
  • Trying to use recursion without child pointers
  • Attempting Morris traversal on parent pointers
  • Using stack without tracking visited nodes
5. Suppose the binary tree nodes can have duplicate values, and you are given preorder and inorder traversals with duplicates. Which modification to the standard iterative approach is necessary to correctly reconstruct the tree?
hard
A. Use a hash map from value to a list of all indices in inorder, and track which index to use next during construction.
B. Ignore duplicates and build the tree as usual, since preorder and inorder uniquely identify the tree.
C. Sort the preorder array to remove duplicates before building the tree.
D. Use a brute force approach with array slicing to handle duplicates correctly.

Solution

  1. Step 1: Understand the problem with duplicates

    Duplicates cause ambiguity in mapping values to inorder indices, breaking the unique root index lookup.
  2. Step 2: Modify data structure

    Store all indices of each value in a list, and track which occurrence to use next to maintain correct subtree boundaries.
  3. Step 3: Avoid naive approaches

    Ignoring duplicates or sorting breaks traversal properties; brute force is inefficient and unnecessary with proper tracking.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Tracking multiple indices per value resolves duplicate ambiguity [OK]
Hint: Track all inorder indices per value to handle duplicates [OK]
Common Mistakes:
  • Assuming unique values always
  • Sorting preorder breaks tree structure
  • Using brute force causes inefficiency
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard