Stage 1 · Code
Trees
Binary Trees
Tree structure, node representation, and basic properties.
5 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Tree Structure
Binary tree — node values in BFS order
A binary tree is a tree where each node has at most two children: left and right. Unlike general trees, binary trees have ordered children (left/right matters).
Node Representation in Go
Gobinary-tree-node.go
10 linesLn 1, Col 1Go
Simple struct with Val, Left, Right. Nil pointers indicate missing children. Use helper to create nodes.
Binary Tree Properties
| Property | Formula/Description |
|---|---|
| Max nodes at level L | 2^L (level 0 = root) |
| Max nodes height h | 2^(h+1) - 1 |
| Min height for n nodes | ⌊log₂(n)⌋ |
| Leaf nodes | Nodes with no children |
| Full binary tree | Every node has 0 or 2 children |
| Complete binary tree | All levels full except last, filled left to right |
| Perfect binary tree | Full + all leaves at same level |
Traversal Overview
| Order | Sequence | Use Case |
|---|---|---|
| Preorder | Root → Left → Right | Copy tree, prefix expression |
| Inorder | Left → Root → Right | BST sorted output |
| Postorder | Left → Right → Root | Delete tree, postfix expression |
| Level-order | Level by level | BFS, shortest path in tree |
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.