Binary Tree

Dec 13, 2025 · 9 min read · binary-tree tree data-structures traversal ·

Share on:

A binary tree is a tree data structure where each node has at most two children, referred to as the left child and right child.

Structure

 1type TreeNode struct {
 2    Val   int
 3    Left  *TreeNode
 4    Right *TreeNode
 5}
 6
 7// Helper to create a node
 8func NewNode(val int) *TreeNode {
 9    return &TreeNode{Val: val}
10}

Visualization

Types of Binary Trees

1. Full Binary Tree

Every node has either 0 or 2 children.

Properties:

If height is $h$, maximum nodes: $2^{h+1} - 1$
If $n$ is total nodes, $i$ is internal nodes, $l$ is leaves: $n = 2i + 1$ and $l = i + 1$

2. Complete Binary Tree

All levels completely filled except possibly the last level, filled from left to right.

Properties:

Height: $h = \lfloor \log_2 n \rfloor$
Used in heap implementation

3. Perfect Binary Tree

All internal nodes have exactly 2 children, all leaves at same level.

Properties:

Total nodes: $n = 2^{h+1} - 1$
Leaves: $2^h$
Internal nodes: $2^h - 1$

4. Balanced Binary Tree

Height of left and right subtrees differ by at most 1.

Balance Factor: $$ BF = \text{height}(\text{left}) - \text{height}(\text{right}) $$

Balanced if: $|BF| \leq 1$ for all nodes

 1func IsBalanced(root *TreeNode) bool {
 2    _, balanced := checkHeight(root)
 3    return balanced
 4}
 5
 6func checkHeight(node *TreeNode) (int, bool) {
 7    if node == nil {
 8        return 0, true
 9    }
10    
11    leftHeight, leftBalanced := checkHeight(node.Left)
12    if !leftBalanced {
13        return 0, false
14    }
15    
16    rightHeight, rightBalanced := checkHeight(node.Right)
17    if !rightBalanced {
18        return 0, false
19    }
20    
21    if abs(leftHeight - rightHeight) > 1 {
22        return 0, false
23    }
24    
25    return 1 + max(leftHeight, rightHeight), true
26}
27
28func abs(x int) int {
29    if x < 0 {
30        return -x
31    }
32    return x
33}

Tree Traversals

In-Order (Left → Root → Right)

 1func InOrder(root *TreeNode) []int {
 2    result := []int{}
 3    inOrderHelper(root, &result)
 4    return result
 5}
 6
 7func inOrderHelper(node *TreeNode, result *[]int) {
 8    if node == nil {
 9        return
10    }
11    
12    inOrderHelper(node.Left, result)
13    *result = append(*result, node.Val)
14    inOrderHelper(node.Right, result)
15}
16
17// Iterative version
18func InOrderIterative(root *TreeNode) []int {
19    result := []int{}
20    stack := []*TreeNode{}
21    curr := root
22    
23    for curr != nil || len(stack) > 0 {
24        // Go to leftmost node
25        for curr != nil {
26            stack = append(stack, curr)
27            curr = curr.Left
28        }
29        
30        // Process node
31        curr = stack[len(stack)-1]
32        stack = stack[:len(stack)-1]
33        result = append(result, curr.Val)
34        
35        // Go to right subtree
36        curr = curr.Right
37    }
38    
39    return result
40}

Use case: For BST, produces sorted sequence

Time: $O(n)$, Space: $O(h)$ where $h$ is height

Pre-Order (Root → Left → Right)

 1func PreOrder(root *TreeNode) []int {
 2    result := []int{}
 3    preOrderHelper(root, &result)
 4    return result
 5}
 6
 7func preOrderHelper(node *TreeNode, result *[]int) {
 8    if node == nil {
 9        return
10    }
11    
12    *result = append(*result, node.Val)
13    preOrderHelper(node.Left, result)
14    preOrderHelper(node.Right, result)
15}
16
17// Iterative version
18func PreOrderIterative(root *TreeNode) []int {
19    if root == nil {
20        return []int{}
21    }
22    
23    result := []int{}
24    stack := []*TreeNode{root}
25    
26    for len(stack) > 0 {
27        node := stack[len(stack)-1]
28        stack = stack[:len(stack)-1]
29        
30        result = append(result, node.Val)
31        
32        // Push right first (so left is processed first)
33        if node.Right != nil {
34            stack = append(stack, node.Right)
35        }
36        if node.Left != nil {
37            stack = append(stack, node.Left)
38        }
39    }
40    
41    return result
42}

Use case: Create copy of tree, prefix expression

Post-Order (Left → Right → Root)

 1func PostOrder(root *TreeNode) []int {
 2    result := []int{}
 3    postOrderHelper(root, &result)
 4    return result
 5}
 6
 7func postOrderHelper(node *TreeNode, result *[]int) {
 8    if node == nil {
 9        return
10    }
11    
12    postOrderHelper(node.Left, result)
13    postOrderHelper(node.Right, result)
14    *result = append(*result, node.Val)
15}

Use case: Delete tree, postfix expression, calculate directory sizes

Level-Order (BFS)

 1func LevelOrder(root *TreeNode) [][]int {
 2    if root == nil {
 3        return [][]int{}
 4    }
 5    
 6    result := [][]int{}
 7    queue := []*TreeNode{root}
 8    
 9    for len(queue) > 0 {
10        levelSize := len(queue)
11        level := []int{}
12        
13        for i := 0; i < levelSize; i++ {
14            node := queue[0]
15            queue = queue[1:]
16            
17            level = append(level, node.Val)
18            
19            if node.Left != nil {
20                queue = append(queue, node.Left)
21            }
22            if node.Right != nil {
23                queue = append(queue, node.Right)
24            }
25        }
26        
27        result = append(result, level)
28    }
29    
30    return result
31}

Time: $O(n)$, Space: $O(w)$ where $w$ is maximum width

Common Operations

1. Height Calculation

1func Height(root *TreeNode) int {
2    if root == nil {
3        return -1 // or 0 depending on definition
4    }
5    
6    return 1 + max(Height(root.Left), Height(root.Right))
7}

Time: $O(n)$

2. Count Nodes

1func CountNodes(root *TreeNode) int {
2    if root == nil {
3        return 0
4    }
5    
6    return 1 + CountNodes(root.Left) + CountNodes(root.Right)
7}

Time: $O(n)$

3. Diameter (Longest Path)

 1func DiameterOfBinaryTree(root *TreeNode) int {
 2    diameter := 0
 3    calculateHeight(root, &diameter)
 4    return diameter
 5}
 6
 7func calculateHeight(node *TreeNode, diameter *int) int {
 8    if node == nil {
 9        return 0
10    }
11    
12    leftHeight := calculateHeight(node.Left, diameter)
13    rightHeight := calculateHeight(node.Right, diameter)
14    
15    // Update diameter if path through this node is longer
16    *diameter = max(*diameter, leftHeight + rightHeight)
17    
18    return 1 + max(leftHeight, rightHeight)
19}

Time: $O(n)$

4. Lowest Common Ancestor

 1func LowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
 2    if root == nil || root == p || root == q {
 3        return root
 4    }
 5    
 6    left := LowestCommonAncestor(root.Left, p, q)
 7    right := LowestCommonAncestor(root.Right, p, q)
 8    
 9    if left != nil && right != nil {
10        return root // Both found in different subtrees
11    }
12    
13    if left != nil {
14        return left
15    }
16    return right
17}

Time: $O(n)$

5. Maximum Path Sum

 1func MaxPathSum(root *TreeNode) int {
 2    maxSum := root.Val
 3    maxPathSumHelper(root, &maxSum)
 4    return maxSum
 5}
 6
 7func maxPathSumHelper(node *TreeNode, maxSum *int) int {
 8    if node == nil {
 9        return 0
10    }
11    
12    // Get max sum from left and right (ignore negative paths)
13    leftMax := max(0, maxPathSumHelper(node.Left, maxSum))
14    rightMax := max(0, maxPathSumHelper(node.Right, maxSum))
15    
16    // Max path through this node
17    pathThroughNode := node.Val + leftMax + rightMax
18    *maxSum = max(*maxSum, pathThroughNode)
19    
20    // Return max path extending from this node
21    return node.Val + max(leftMax, rightMax)
22}

Time: $O(n)$

6. Serialize and Deserialize

 1import "strconv"
 2import "strings"
 3
 4func Serialize(root *TreeNode) string {
 5    if root == nil {
 6        return "null"
 7    }
 8    
 9    return strconv.Itoa(root.Val) + "," + 
10           Serialize(root.Left) + "," + 
11           Serialize(root.Right)
12}
13
14func Deserialize(data string) *TreeNode {
15    values := strings.Split(data, ",")
16    index := 0
17    return deserializeHelper(&values, &index)
18}
19
20func deserializeHelper(values *[]string, index *int) *TreeNode {
21    if *index >= len(*values) || (*values)[*index] == "null" {
22        *index++
23        return nil
24    }
25    
26    val, _ := strconv.Atoi((*values)[*index])
27    *index++
28    
29    node := &TreeNode{Val: val}
30    node.Left = deserializeHelper(values, index)
31    node.Right = deserializeHelper(values, index)
32    
33    return node
34}

Time: $O(n)$

7. Invert Tree (Mirror)

 1func InvertTree(root *TreeNode) *TreeNode {
 2    if root == nil {
 3        return nil
 4    }
 5    
 6    // Swap children
 7    root.Left, root.Right = root.Right, root.Left
 8    
 9    // Recursively invert subtrees
10    InvertTree(root.Left)
11    InvertTree(root.Right)
12    
13    return root
14}

Time: $O(n)$

Binary Search Tree (BST)

A binary tree where for each node:

All values in left subtree < node value
All values in right subtree > node value

BST Operations

 1// Insert
 2func Insert(root *TreeNode, val int) *TreeNode {
 3    if root == nil {
 4        return &TreeNode{Val: val}
 5    }
 6    
 7    if val < root.Val {
 8        root.Left = Insert(root.Left, val)
 9    } else {
10        root.Right = Insert(root.Right, val)
11    }
12    
13    return root
14}
15
16// Search
17func Search(root *TreeNode, val int) *TreeNode {
18    if root == nil || root.Val == val {
19        return root
20    }
21    
22    if val < root.Val {
23        return Search(root.Left, val)
24    }
25    return Search(root.Right, val)
26}
27
28// Delete
29func DeleteNode(root *TreeNode, key int) *TreeNode {
30    if root == nil {
31        return nil
32    }
33    
34    if key < root.Val {
35        root.Left = DeleteNode(root.Left, key)
36    } else if key > root.Val {
37        root.Right = DeleteNode(root.Right, key)
38    } else {
39        // Node to delete found
40        if root.Left == nil {
41            return root.Right
42        }
43        if root.Right == nil {
44            return root.Left
45        }
46        
47        // Node has two children: get inorder successor
48        minNode := findMin(root.Right)
49        root.Val = minNode.Val
50        root.Right = DeleteNode(root.Right, minNode.Val)
51    }
52    
53    return root
54}
55
56func findMin(node *TreeNode) *TreeNode {
57    for node.Left != nil {
58        node = node.Left
59    }
60    return node
61}
62
63// Validate BST
64func IsValidBST(root *TreeNode) bool {
65    return isValidBSTHelper(root, nil, nil)
66}
67
68func isValidBSTHelper(node *TreeNode, min, max *int) bool {
69    if node == nil {
70        return true
71    }
72    
73    if (min != nil && node.Val <= *min) || (max != nil && node.Val >= *max) {
74        return false
75    }
76    
77    return isValidBSTHelper(node.Left, min, &node.Val) &&
78           isValidBSTHelper(node.Right, &node.Val, max)
79}

BST Time Complexity:

Search/Insert/Delete: $O(h)$ where $h$ is height
Best case (balanced): $O(\log n)$
Worst case (skewed): $O(n)$

Complexity Summary

Operation	Time	Space
Traversal	$O(n)$	$O(h)$
Height	$O(n)$	$O(h)$
Count Nodes	$O(n)$	$O(h)$
Search (general)	$O(n)$	$O(h)$
Search (BST)	$O(h)$	$O(h)$
Insert (BST)	$O(h)$	$O(h)$
Delete (BST)	$O(h)$	$O(h)$

where $h$ is height: $O(\log n)$ for balanced, $O(n)$ for skewed

Helper Functions

 1func max(a, b int) int {
 2    if a > b {
 3        return a
 4    }
 5    return b
 6}
 7
 8func min(a, b int) int {
 9    if a < b {
10        return a
11    }
12    return b
13}

Related Snippets

Binary Search
Binary search is an efficient algorithm for finding a target value in a sorted …
General Tree
A tree is a hierarchical data structure consisting of nodes connected by edges, …
Heap Data Structure
A heap is a specialized tree-based data structure that satisfies the heap …
Heap Sort
Heap sort is a comparison-based sorting algorithm that uses a binary heap data …
Linked List Operations
Optimal techniques for common linked list operations using pointer manipulation, …
LRU and LFU Cache
Cache replacement policies determine which items to evict when the cache is …
Merge Sort
Merge sort is a stable, comparison-based sorting algorithm that uses the …
Quadtree
A Quadtree is a tree data structure where each internal node has exactly four …
Quick Sort
Quick sort is an efficient, in-place, comparison-based sorting algorithm that …
String Similarity Algorithms
Algorithms for measuring similarity between strings, used in spell checking, DNA …
Terrain & Heightmap Generation
Procedural terrain generation creates realistic landscapes using mathematical …
Trie (Prefix Tree)
A Trie (pronounced "try") is a tree-like data structure used to store …
Wave Function Collapse
Wave Function Collapse (WFC) is a procedural generation algorithm that creates …