7.1 Binary trees¶

A binary tree is a nonlinear data structure representing relationships between ancestors and descendants. It embodies the divide-and-conquer idea of splitting in two. Like a linked list, it is built from nodes, each containing a value and references to its left and right children.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

class TreeNode:
    """Binary tree node class"""
    def __init__(self, val: int):
        self.val: int = val                # Node value
        self.left: TreeNode | None = None  # Left child reference
        self.right: TreeNode | None = None # Right child reference

/* Binary tree node struct */
struct TreeNode {
    int val;          // Node value
    TreeNode *left;   // Left child pointer
    TreeNode *right;  // Right child pointer
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

/* Binary tree node class */
class TreeNode {
    int val;         // Node value
    TreeNode left;   // Left child reference
    TreeNode right;  // Right child reference
    TreeNode(int x) { val = x; }
}

/* Binary tree node class */
class TreeNode(int? x) {
    public int? val = x;    // Node value
    public TreeNode? left;  // Left child reference
    public TreeNode? right; // Right child reference
}

/* Binary tree node struct */
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
/* Constructor */
func NewTreeNode(v int) *TreeNode {
    return &TreeNode{
        Left:  nil, // Left child pointer
        Right: nil, // Right child pointer
        Val:   v,   // Node value
    }
}

/* Binary tree node class */
class TreeNode {
    var val: Int // Node value
    var left: TreeNode? // Left child reference
    var right: TreeNode? // Right child reference

    init(x: Int) {
        val = x
    }
}

/* Binary tree node class */
class TreeNode {
    val; // Node value
    left; // Left child pointer
    right; // Right child pointer
    constructor(val, left, right) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

/* Binary tree node class */
class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val; // Node value
        this.left = left === undefined ? null : left; // Left child reference
        this.right = right === undefined ? null : right; // Right child reference
    }
}

/* Binary tree node class */
class TreeNode {
  int val;         // Node value
  TreeNode? left;  // Left child reference
  TreeNode? right; // Right child reference
  TreeNode(this.val, [this.left, this.right]);
}

use std::rc::Rc;
use std::cell::RefCell;

/* Binary tree node struct */
struct TreeNode {
    val: i32,                               // Node value
    left: Option<Rc<RefCell<TreeNode>>>,    // Left child reference
    right: Option<Rc<RefCell<TreeNode>>>,   // Right child reference
}

impl TreeNode {
    /* Constructor */
    fn new(val: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Self {
            val,
            left: None,
            right: None
        }))
    }
}

/* Binary tree node struct */
typedef struct TreeNode {
    int val;                // Node value
    int height;             // Node height
    struct TreeNode *left;  // Left child pointer
    struct TreeNode *right; // Right child pointer
} TreeNode;

/* Constructor */
TreeNode *newTreeNode(int val) {
    TreeNode *node;

    node = (TreeNode *)malloc(sizeof(TreeNode));
    node->val = val;
    node->height = 0;
    node->left = NULL;
    node->right = NULL;
    return node;
}

/* Binary tree node class */
class TreeNode(val _val: Int) {  // Node value
    var left: TreeNode? = null   // Left child reference
    var right: TreeNode? = null  // Right child reference
}

### Binary tree node class ###
class TreeNode
  attr_accessor :val    # Node value
  attr_accessor :left   # Left child reference
  attr_accessor :right  # Right child reference

  def initialize(val)
    @val = val
  end
end

Each node has two references or pointers, one to its left child and one to its right child. The node is their parent. Its left child and all nodes below that child form its left subtree; the right subtree is defined similarly.

Every non-leaf node has children and at least one nonempty subtree. In Figure 7-1, if node 2 is the parent, its left and right children are nodes 4 and 5. Its left subtree consists of node 4 and everything below it, and its right subtree consists of node 5 and everything below it.

Parents, children, and subtrees

Figure 7-1 Parents, children, and subtrees

7.1.1 Common terminology¶

Figure 7-2 illustrates common binary-tree terminology.

Root: the topmost node, which has no parent.
Leaf: a node with no children; both of its child references point to None.
Edge: a connection between two nodes, represented by a reference or pointer.
A node's level: levels increase from top to bottom, with the root at level 1.
A node's degree: its number of children, which is 0, 1, or 2 in a binary tree.
A tree's height: the number of edges from the root to its farthest leaf.
A node's depth: the number of edges from the root to that node.
A node's height: the number of edges from that node to its farthest leaf.

Common binary-tree terminology

Figure 7-2 Common binary-tree terminology

Tip

Height and depth are usually measured in edges, but some problems or textbooks count nodes instead. Under that convention, add 1 to both height and depth.

7.1.2 Basic operations¶

1. Initializing a binary tree¶

As with a linked list, first create the nodes, then connect them with references or pointers.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

binary_tree.py

# Initialize a binary tree
# Initialize nodes
n1 = TreeNode(val=1)
n2 = TreeNode(val=2)
n3 = TreeNode(val=3)
n4 = TreeNode(val=4)
n5 = TreeNode(val=5)
# Connect nodes with references (pointers)
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5

binary_tree.cpp

/* Initialize a binary tree */
// Initialize nodes
TreeNode* n1 = new TreeNode(1);
TreeNode* n2 = new TreeNode(2);
TreeNode* n3 = new TreeNode(3);
TreeNode* n4 = new TreeNode(4);
TreeNode* n5 = new TreeNode(5);
// Connect nodes with references (pointers)
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;

binary_tree.java

// Initialize nodes
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
// Connect nodes with references (pointers)
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

binary_tree.cs

/* Initialize a binary tree */
// Initialize nodes
TreeNode n1 = new(1);
TreeNode n2 = new(2);
TreeNode n3 = new(3);
TreeNode n4 = new(4);
TreeNode n5 = new(5);
// Connect nodes with references (pointers)
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

binary_tree.go

/* Initialize a binary tree */
// Initialize nodes
n1 := NewTreeNode(1)
n2 := NewTreeNode(2)
n3 := NewTreeNode(3)
n4 := NewTreeNode(4)
n5 := NewTreeNode(5)
// Connect nodes with references (pointers)
n1.Left = n2
n1.Right = n3
n2.Left = n4
n2.Right = n5

binary_tree.swift

// Initialize nodes
let n1 = TreeNode(x: 1)
let n2 = TreeNode(x: 2)
let n3 = TreeNode(x: 3)
let n4 = TreeNode(x: 4)
let n5 = TreeNode(x: 5)
// Connect nodes with references (pointers)
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5

binary_tree.js

/* Initialize a binary tree */
// Initialize nodes
let n1 = new TreeNode(1),
    n2 = new TreeNode(2),
    n3 = new TreeNode(3),
    n4 = new TreeNode(4),
    n5 = new TreeNode(5);
// Connect nodes with references (pointers)
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

binary_tree.ts

/* Initialize a binary tree */
// Initialize nodes
let n1 = new TreeNode(1),
    n2 = new TreeNode(2),
    n3 = new TreeNode(3),
    n4 = new TreeNode(4),
    n5 = new TreeNode(5);
// Connect nodes with references (pointers)
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

binary_tree.dart

/* Initialize a binary tree */
// Initialize nodes
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
// Connect nodes with references (pointers)
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

binary_tree.rs

// Initialize nodes
let n1 = TreeNode::new(1);
let n2 = TreeNode::new(2);
let n3 = TreeNode::new(3);
let n4 = TreeNode::new(4);
let n5 = TreeNode::new(5);
// Connect nodes with references (pointers)
n1.borrow_mut().left = Some(n2.clone());
n1.borrow_mut().right = Some(n3);
n2.borrow_mut().left = Some(n4);
n2.borrow_mut().right = Some(n5);

binary_tree.c

/* Initialize a binary tree */
// Initialize nodes
TreeNode *n1 = newTreeNode(1);
TreeNode *n2 = newTreeNode(2);
TreeNode *n3 = newTreeNode(3);
TreeNode *n4 = newTreeNode(4);
TreeNode *n5 = newTreeNode(5);
// Connect nodes with references (pointers)
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;

binary_tree.kt

// Initialize nodes
val n1 = TreeNode(1)
val n2 = TreeNode(2)
val n3 = TreeNode(3)
val n4 = TreeNode(4)
val n5 = TreeNode(5)
// Connect nodes with references (pointers)
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5

binary_tree.rb

# Initialize a binary tree
# Initialize nodes
n1 = TreeNode.new(1)
n2 = TreeNode.new(2)
n3 = TreeNode.new(3)
n4 = TreeNode.new(4)
n5 = TreeNode.new(5)
# Connect nodes with references (pointers)
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5

Visualize execution

View full screen >

2. Inserting and deleting nodes¶

As with linked lists, insertion and deletion can be implemented by changing pointers. An example is shown below.

Inserting and deleting a binary-tree node

Figure 7-3 Inserting and deleting a binary-tree node

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

binary_tree.py

# Insert and delete a node
p = TreeNode(0)
# Insert node P between n1 and n2
n1.left = p
p.left = n2
# Delete node P
n1.left = n2

binary_tree.cpp

/* Insert and delete a node */
TreeNode* P = new TreeNode(0);
// Insert node P between n1 and n2
n1->left = P;
P->left = n2;
// Delete node P
n1->left = n2;
// Free the memory
delete P;

binary_tree.java

TreeNode P = new TreeNode(0);
// Insert node P between n1 and n2
n1.left = P;
P.left = n2;
// Delete node P
n1.left = n2;

binary_tree.cs

/* Insert and delete a node */
TreeNode P = new(0);
// Insert node P between n1 and n2
n1.left = P;
P.left = n2;
// Delete node P
n1.left = n2;

binary_tree.go

/* Insert and delete a node */
// Insert node P between n1 and n2
p := NewTreeNode(0)
n1.Left = p
p.Left = n2
// Delete node P
n1.Left = n2

binary_tree.swift

let P = TreeNode(x: 0)
// Insert node P between n1 and n2
n1.left = P
P.left = n2
// Delete node P
n1.left = n2

binary_tree.js

/* Insert and delete a node */
let P = new TreeNode(0);
// Insert node P between n1 and n2
n1.left = P;
P.left = n2;
// Delete node P
n1.left = n2;

binary_tree.ts

/* Insert and delete a node */
const P = new TreeNode(0);
// Insert node P between n1 and n2
n1.left = P;
P.left = n2;
// Delete node P
n1.left = n2;

binary_tree.dart

/* Insert and delete a node */
TreeNode P = new TreeNode(0);
// Insert node P between n1 and n2
n1.left = P;
P.left = n2;
// Delete node P
n1.left = n2;

binary_tree.rs

let p = TreeNode::new(0);
// Insert node P between n1 and n2
n1.borrow_mut().left = Some(p.clone());
p.borrow_mut().left = Some(n2.clone());
// Delete node p
n1.borrow_mut().left = Some(n2);

binary_tree.c

/* Insert and delete a node */
TreeNode *P = newTreeNode(0);
// Insert node P between n1 and n2
n1->left = P;
P->left = n2;
// Delete node P
n1->left = n2;
// Free the memory
free(P);

binary_tree.kt

val P = TreeNode(0)
// Insert node P between n1 and n2
n1.left = P
P.left = n2
// Delete node P
n1.left = n2

binary_tree.rb

# Insert and delete a node
_p = TreeNode.new(0)
# Insert node _p between n1 and n2
n1.left = _p
_p.left = n2
# Delete the node
n1.left = n2

Visualize execution

View full screen >

Tip

Inserting a node may change the tree's logical structure, while deleting a node generally means deleting it and all its subtrees. Meaningful insertion and deletion operations therefore usually require several coordinated steps.

7.1.3 Common types of binary trees¶

1. Perfect binary trees¶

In a perfect binary tree, every level is completely filled, as shown below. Leaves have degree \(0\), and all other nodes have degree \(2\). A tree of height \(h\) has \(2^{h+1} - 1\) nodes, an exponential relationship reminiscent of cell division in nature.

Tip

In Chinese-language resources, a perfect binary tree is often called 满二叉树.

A perfect binary tree

Figure 7-4 A perfect binary tree

2. Complete binary trees¶

Only the lowest level of a complete binary tree may be incomplete, and its nodes must fill that level consecutively from left to right, as shown below. Every perfect binary tree is also complete.

A complete binary tree

Figure 7-5 A complete binary tree

3. Full binary trees¶

In a full binary tree, every node other than a leaf has exactly two children, as shown below.

A full binary tree

Figure 7-6 A full binary tree

4. Balanced binary trees¶

In a balanced binary tree, the heights of the left and right subtrees of every node differ by at most 1, as shown below.

A balanced binary tree

Figure 7-7 A balanced binary tree

7.1.4 Degeneration of a binary tree¶

Figure 7-8 shows ideal and degenerate tree structures. When every level is full, the tree is perfect. When every node lies along one side, the tree degenerates into a linked list.

A perfect binary tree is the ideal case, making full use of divide and conquer.
A linked list is the opposite extreme: operations become linear, with time complexity degrading to \(O(n)\).

Best and worst binary-tree structures

Figure 7-8 Best and worst binary-tree structures

As Table 7-1 shows, quantities such as leaf count, total node count, and height reach their maximum or minimum values in these best and worst structures.

Table 7-1 Best and worst binary-tree structures

	Perfect binary tree	Linked list
Nodes at level \(i\)	\(2^{i-1}\)	\(1\)
Leaves in a tree of height \(h\)	\(2^h\)	\(1\)
Total nodes in a tree of height \(h\)	\(2^{h+1} - 1\)	\(h + 1\)
Height of a tree with \(n\) nodes	\(\log_2 (n+1) - 1\)	\(n - 1\)

7.1 Binary trees¶

7.1.1 Common terminology¶

7.1.2 Basic operations¶

1. Initializing a binary tree¶

2. Inserting and deleting nodes¶

7.1.3 Common types of binary trees¶

1. Perfect binary trees¶

2. Complete binary trees¶

3. Full binary trees¶

4. Balanced binary trees¶

7.1.4 Degeneration of a binary tree¶

Share your insights, questions, or suggestions in the comments