Micro-questions over the binary trees module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. The definition

1. What is a binary tree?

Answer

A tree in which every node has at most two children, named the left child and the right child.

2. Is that the whole definition?

Answer

Yes. There is no rule about values, no ordering requirement and no balance requirement. Ordering makes a binary search tree; balance is what makes it fast.

3. Does it matter which child is left and which is right?

Answer

Yes. Swapping them gives a different tree, even with the same values present — and an in-order traversal will show it.

4. Write the node class.

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

5. Why does shape matter so much?

Answer

A tree’s shape directly dictates its performance — when short, when it degenerates into a line.


B. The five shapes

6. What is a full (proper) binary tree?

Answer

Every node has either 0 or 2 children. No node has exactly one.

7. Where are full binary trees used?

Answer

Arithmetic expression trees — operators take 2 operands, numbers take 0, so no node can have exactly one child.

8. What is a complete binary tree?

Answer

Every level completely filled except possibly the last, which is filled strictly from left to right.

9. Where are complete binary trees used, and why?

Answer

Heaps and priority queues. Because there are no gaps, a complete tree can be stored in a flat array with no pointers at all.

10. What is a perfect binary tree?

Answer

All internal nodes have 2 children and all leaves sit at the exact same depth.

11. Give the node-count formula for a perfect tree of height .

Answer

For height 2: nodes.

12. What is a balanced binary tree?

Answer

One where the heights of the left and right subtrees of every node differ by at most 1.

13. Why does balance matter?

Answer

It keeps height bounded to , which is what guarantees fast searches.

14. What is a degenerate (pathological) binary tree?

Answer

Every node has only one child — the tree degrades into a straight line.

15. Why is a degenerate tree dangerous?

Answer

It is structurally identical to a linked list. Height becomes and every operation slows from to .


C. Telling the shapes apart

16. What is the difference between full and complete?

Answer

Full is about the number of children — 0 or 2. Complete is about where the gaps are — only at the end of the last level. A tree can be either one without being the other.

17. Is a perfect tree also full and complete?

Answer

Yes, both. Perfect is the strictest shape — no gaps anywhere and every internal node with two children.

18. Give a tree that is complete but not full.

Answer
     1
    / \
   2   3
  /
 4

Node 2 has exactly one child, so it is not full; the last level fills from the left, so it is complete.

19. Give a tree that is full but not complete.

Answer
     1
    / \
   2   3
      / \
     4   5

Every node has 0 or 2 children (full), but the last level’s gap is on the left rather than filled left-to-right (not complete).


D. The shape checks

20. How do you test for full?

Answer

A node fails if exactly one child is None. Recurse both sides; an empty tree is vacuously full.

if (node.left is None) != (node.right is None):
    return False

21. How do you test for perfect without walking every level?

Answer

By the numbers: count_nodes(root) == 2**(height(root)+1) - 1. No other shape hits that count.

22. What is the clean check for complete?

Answer

A level-order walk that enqueues None children too: once you have seen a gap, you must never see another real node.

23. Why is the naive balance check ?

Answer

It calls height() from inside the recursion, recomputing the same subtree heights over and over at every level.

24. How does the one-pass balance check work?

Answer

The helper returns the height and a sentinel (-2) meaning “already unbalanced below here”. One traversal, , with failure propagating straight up.

25. How do you test for degenerate?

Answer

Every node has at most one child — fail if any node has both.


E. Complete trees in an array

26. Why can a complete tree live in a flat array?

Answer

Because it has no gaps except at the end, you can number nodes level by level, left to right, and store them at exactly those positions with nothing missing in between.

27. Give the three index formulas.

Answer

Left child of : .
Right child of : .
Parent of : .

28. What two things does the array layout save?

Answer

The memory of two pointers per node, and the cache misses — the whole tree sits in one contiguous block, so walking it is cache-friendly in a way a pointer-based tree never is.

29. What is the catch?

Answer

It only works while the tree stays complete. One gap in the middle and every later position shifts, breaking the arithmetic.

30. How does a heap guarantee it stays complete?

Answer

By construction: inserting always adds at the next free array slot, and removing always takes the last one.

31. Why can a BST not be stored this way?

Answer

Its shape is dictated by the order keys arrive in, not chosen. A lopsided BST would leave most of the array empty.


F. Traps

32. Does “binary tree” imply ordering?

Answer

No. A heap and an expression tree are both binary and neither is sorted.

33. What is the empty-tree height convention here, and why does it matter?

Answer

height(None) = -1, so a single node has height 0. Some books use 0 for empty and 1 for a single node. Neither is wrong — mixing the two produces off-by-one errors everywhere.

34. Are two trees with the same values the same tree?

Answer

No. Left and right are not interchangeable, so mirrored positions give a genuinely different tree.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Trees