learningto/pass

Binary Trees

IntermediateData Structures

Trees underlie databases, file systems, and compilers. Google frequently tests tree traversals, LCA, serialization, and BST properties. Master both recursive and iterative approaches.

AVG TIME
O(log n)
SPACE
O(h)
BEST
O(log n)
WORST
O(n)

Key Concepts

  • 1Inorder traversal of BST yields sorted sequence
  • 2DFS with recursion is elegant; iterative uses explicit stack
  • 3LCA (Lowest Common Ancestor): recurse, look for two target nodes
  • 4Tree height/depth: max(left, right) + 1
  • 5Level-order (BFS) uses a queue, processes nodes layer by layer

In Python

Concept to Code- 1 structure for this topic
declare
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
common ops
node.left
O(1)
node.right
O(1)
not node.left and not node.right
O(1)
say in interview
"I'll use a TreeNode class (usually provided in the problem)"
No built-in tree in Python. The node class is almost always given to you in the problem stub.

Math You Need For This

Imagine a "yes/no" game. Is the answer bigger or smaller than 50? Bigger. Bigger or smaller than 75? Smaller. Each question eliminates half the remaining possibilities.

Required concepts
Key math ideas
1 / 3

Logarithms - "how many times can you cut in half?"

log₂(n) answers this question: if you start with n things and keep cutting the group in half, how many cuts until you reach 1? For 1,024 items that is only 10 cuts. For a million items it is about 20. The number barely grows even as n explodes.

Remaining1024 items (log₂(1024) = 10)
Clicks so far: 0

Think of it this way: A phone book with 1,024 names. Flip to the middle - is your name before or after? Flip to the middle of the surviving half. Repeat. You find any name in at most 10 flips, not 1,024.

For algorithms: Any algorithm that cuts its remaining work in half each step runs in O(log n). Binary search, balanced tree lookups, and heap operations all work this way.

Interactive 3D Visualization

Binary Tree (BST)
Search: O(log n)Insert: O(log n)Space: O(n)
Drag to orbit - Scroll to zoom

Python Implementation

example.py
Loading...
Now try it yourself
2 challenges with test cases and AI feedback
Practice Now

Complexity Analysis

1481216n²nlog n1n (input size)
COMMON OPERATIONS
Array
Access:O(1)
Search:O(n)
Insert end:O(1)*
Insert mid:O(n)
Hash Map
Get/Set:O(1)*
Delete:O(1)*
Search value:O(n)
Iterate:O(n)
Linked List
Access:O(n)
Search:O(n)
Insert head:O(1)
Delete known:O(1)
Binary Search
Search:O(log n)
Insert:O(log n)
Balanced BST
Search:O(log n)
Insert:O(log n)
Delete:O(log n)
Heap
Peek min/max:O(1)
Push:O(log n)
Pop:O(log n)
Heapify:O(n)
Graph (BFS/DFS)
Traversal:O(V+E)
Dijkstra (heap):O((V+E) log V)
Merge / Quick Sort
Sort:O(n log n)
Space (merge):O(n)
Space (quick):O(log n)

* amortized average case

READY TO TEST YOURSELF?

Put Binary Trees into practice

The best way to lock in what you've learned is to write code. Solve real interview-style problems right now.

Next: Graphs
Binary Trees
Next: Graphs