Types of Binary Trees

In problem-solving, binary trees primarily come in two main forms: Full Binary Trees and Complete Binary Trees.

Full Binary Tree

A Full Binary Tree is a binary tree in which every node has either zero or two children, and all leaf nodes (nodes with degree 0) are at the same level.

This binary tree is a Full Binary Tree, which can also be described as a binary tree of depth k that contains 2^k - 1 nodes.

        graph TD
        A((1)) --> B((2))
        A --> C((3))
        B --> D((4))
        B --> E((5))
        C --> F((6))
        C --> G((7))
    
        style A fill:#f9f,stroke:#333,stroke-width:2px
        style B fill:#bbf,stroke:#333,stroke-width:2px
        style C fill:#bbf,stroke:#333,stroke-width:2px
        style D fill:#ddf,stroke:#333,stroke-width:2px
        style E fill:#ddf,stroke:#333,stroke-width:2px
        style F fill:#ddf,stroke:#333,stroke-width:2px
        style G fill:#ddf,stroke:#333,stroke-width:2px

Complete Binary Tree

A Complete Binary Tree is defined as follows:

In a complete binary tree, all levels except the last one are completely filled with nodes. The last level may not be completely filled, but all nodes at this level are positioned as far left as possible.

If the lowest level is the h-th level (with h starting from 1), then this level contains 1 to 2^{(h-1)} nodes.

Make sure to carefully review the definition of a complete binary tree, as many people do not fully understand it.

Here’s a typical example to illustrate:

    graph TD
subgraph "Valid Complete Binary Tree"
    A1[1]
    B1[2] & B2[3]
    C1[4] & C2[5] & C3[6] & C4[7]
    A1 --> B1 & B2
    B1 --> C1 & C2
    B2 --> C3 & C4
    style A1 fill:#98FB98
    style B1 fill:#98FB98
    style B2 fill:#98FB98
    style C1 fill:#98FB98
    style C2 fill:#98FB98
    style C3 fill:#98FB98
    style C4 fill:#98FB98
end

subgraph "Valid Complete Binary Tree"
    D1[1]
    E1[2] & E2[3]
    F1[4] & F2[5] & F3[6]
    D1 --> E1 & E2
    E1 --> F1 & F2
    E2 --> F3
    style D1 fill:#98FB98
    style E1 fill:#98FB98
    style E2 fill:#98FB98
    style F1 fill:#98FB98
    style F2 fill:#98FB98
    style F3 fill:#98FB98
end

subgraph "Invalid Complete Binary Tree"
    G1[1]
    H1[2] & H2[3]
    I2[5] & I3[6]
    G1 --> H1 & H2
    H1 --> I2
    H2 --> I3
    style G1 fill:#FFB6C1
    style H1 fill:#FFB6C1
    style H2 fill:#FFB6C1
    style I2 fill:#FFB6C1
    style I3 fill:#FFB6C1
end

I believe many of you may have struggled with determining whether the last binary tree is a complete binary tree or not.

Earlier, we discussed that a priority queue is essentially a heap, and a heap is a complete binary tree while also maintaining the order relationship between parent and child nodes.

Stacks and Queues Summary
This blog post provides a summary of stacks and queues in Python, covering their implementations, applications, and optimization strategies. Explore efficient solutions for classic problems about stacks and queues with Python examples and expert tips.
Fanyang Meng's BlogFanyang Meng

Binary Search Tree

The trees we introduced earlier did not contain numerical values. However, a Binary Search Tree (BST) is an ordered tree with specific properties:

  • If a node has a left subtree, then all nodes in the left subtree have values less than the value of the root node.
  • If a node has a right subtree, then all nodes in the right subtree have values greater than the value of the root node.
  • Both the left and right subtrees must also be binary search trees.

The following two trees are examples of Binary Search Trees (BSTs):

graph TD
    subgraph "Valid BST Example"
        A1[5]
        B1[3] & B2[7]
        C1[1] & C2[4] & C3[6] & C4[8]
        
        A1 --> B1
        A1 --> B2
        B1 --> C1
        B1 --> C2
        B2 --> C3
        B2 --> C4
        
        style A1 fill:#98FB98
        style B1 fill:#98FB98
        style B2 fill:#98FB98
        style C1 fill:#98FB98
        style C2 fill:#98FB98
        style C3 fill:#98FB98
        style C4 fill:#98FB98
        
        %% Add annotations
        note1[All nodes < 5] -.-> B1
        note2[All nodes > 5] -.-> B2
        style note1 fill:#f9f,stroke:#333,stroke-width:2px
        style note2 fill:#f9f,stroke:#333,stroke-width:2px
    end

    subgraph "Valid BST Example"
        D1[10]
        E1[5] & E2[15]
        F1[3] & F2[7]
        
        D1 --> E1
        D1 --> E2
        E1 --> F1
        E1 --> F2
        
        style D1 fill:#98FB98
        style E1 fill:#98FB98
        style E2 fill:#98FB98
        style F1 fill:#98FB98
        style F2 fill:#98FB98
        
        %% Add annotations
        note3[All nodes < 10] -.-> E1
        note4[All nodes > 10] -.-> E2
        style note3 fill:#f9f,stroke:#333,stroke-width:2px
        style note4 fill:#f9f,stroke:#333,stroke-width:2px
    end

Balanced Binary Search Tree

A Balanced Binary Search Tree (BST), also known as an AVL Tree (named after Adelson-Velsky and Landis), has the following properties:

  • It is either an empty tree or
  • The absolute height difference between its left and right subtrees does not exceed 1.
  • Both the left and right subtrees must also be balanced binary search trees.

Illustration:

  graph TD
    subgraph "Valid Balanced BST 1"
        A1[10
h=2]
        B1[5
h=1] & B2[15
h=1]
        C1[3
h=0] & C2[7
h=0] & C3[13
h=0] & C4[17
h=0]
        
        A1 --> B1
        A1 --> B2
        B1 --> C1
        B1 --> C2
        B2 --> C3
        B2 --> C4
        
        note1["Height diff = 0
(balanced)"] -.-> A1
        
        style A1 fill:#98FB98
        style B1 fill:#98FB98
        style B2 fill:#98FB98
        style C1 fill:#98FB98
        style C2 fill:#98FB98
        style C3 fill:#98FB98
        style C4 fill:#98FB98
    end

    subgraph "Valid Balanced BST 2"
        D1[10
h=2]
        E1[5
h=1] & E2[15
h=0]
        F1[3
h=0] & F2[7
h=0]
        
        D1 --> E1
        D1 --> E2
        E1 --> F1
        E1 --> F2
        
        note2["Height diff = 1
(balanced)"] -.-> D1
        
        style D1 fill:#98FB98
        style E1 fill:#98FB98
        style E2 fill:#98FB98
        style F1 fill:#98FB98
        style F2 fill:#98FB98
    end

    subgraph "Invalid Balanced BST"
        G1[10
h=3]
        H1[5
h=2] & H2[15
h=0]
        I1[3
h=1]
        J1[1
h=0]
        
        G1 --> H1
        G1 --> H2
        H1 --> I1
        I1 --> J1
        
        note3["Height diff = 2
(unbalanced)"] -.-> G1
        
        style G1 fill:#FFB6C1
        style H1 fill:#FFB6C1
        style H2 fill:#FFB6C1
        style I1 fill:#FFB6C1
        style J1 fill:#FFB6C1
    end

    %% Add style to notes
    style note1 fill:#f9f,stroke:#333,stroke-width:2px
    style note2 fill:#f9f,stroke:#333,stroke-width:2px
    style note3 fill:#f9f,stroke:#333,stroke-width:2px

Binary Tree Storage Methods

A binary tree can be stored in two ways:

  • Linked Storage (using pointers)
  • Sequential Storage (using arrays)

Linked Storage vs. Sequential Storage

  • Linked Storage: Uses pointers to connect nodes that may be stored at different memory addresses.
  • Sequential Storage: Uses an array where elements are stored contiguously in memory.

As the name suggests, sequential storage ensures that elements are stored continuously in memory, whereas linked storage connects nodes distributed across different memory locations using pointers.

Illustration of Linked Storage:

  graph TD
    Root[Node Element] --- LP1[Left Pointer]
    Root --- RP1[Right Pointer]
    
    LP1 --> Node1[Node Element]
    RP1 --> Node2[Node Element]
    
    Node1 --- LP2[Left Pointer]
    Node1 --- RP2[Right Pointer]
    Node2 --- LP3[Left Pointer]
    Node2 --- RP3[Right Pointer]
    
    LP2 --> NULL1[NULL]
    RP2 --> NULL2[NULL]
    LP3 --> NULL3[NULL]
    RP3 --> NULL4[NULL]

Linked storage is a familiar method for most people, but now let’s take a look at how sequential storage works.

In sequential storage, a binary tree is stored using an array.

How Does Sequential Storage Work?

  • Each node’s position in the tree corresponds to an index in the array.
  • The root node is stored at index 0 (or index 1, depending on the implementation).
  • For a node stored at index i:
    • The left child is at index 2i + 1.
    • The right child is at index 2i + 2.

This method efficiently stores complete binary trees, ensuring that elements are contiguously placed in memory.

Illustration of sequential storage: (Refer to the provided diagram)

  graph TD
    %% Tree structure
    A["a (0)"] --> B["b (1)"]
    A --> C["c (2)"]
    B --> D["d (3)"]
    B --> E["e (4)"]
    C --> F["f (5)"]
    C --> G["g (6)"]
    
    %% Array representation
    subgraph Array["Array Representation"]
        direction LR
        AA[a] --- BB[b] --- CC[c] --- DD[d] --- EE[e] --- FF[f] --- GG[g]
    end
    
    %% Index representation
    subgraph Index["Index"]
        direction LR
        I0[0] --- I1[1] --- I2[2] --- I3[3] --- I4[4] --- I5[5] --- I6[6]
    end
    
    %% Positioning the arrays below the tree
    A ~~~ Array
    Array ~~~ Index
    
    %% Styling
    classDef default fill:#F78B8B,stroke:#333,stroke-width:2px
    classDef array fill:white,stroke:black
    classDef index fill:white,stroke:none
    
    class AA,BB,CC,DD,EE,FF,GG array
    class I0,I1,I2,I3,I4,I5,I6 index

However, using a linked representation (with pointers) is generally more intuitive and easier to manipulate, which is why binary trees are usually stored in a linked structure rather than an array.

That being said, it’s important to understand that arrays can also be used to represent binary trees effectively, especially when dealing with complete binary trees or heaps.

Binary Tree Traversal Methods

To fully understand binary tree traversal, it’s essential to know the fundamental traversal techniques.

Some people may have solved numerous binary tree problems and are familiar with pre-order, in-order, and post-order traversal, as well as level-order traversal, but they lack a structured framework.

Here, I will list the different types of binary tree traversal so that you can see how they are all connected.

Two Main Traversal Methods

  1. Depth-First Traversal (DFS) – Moves deeper into the tree first and backtracks after reaching a leaf node.
  2. Breadth-First Traversal (BFS) – Traverses level by level.
These two traversal methods form the foundation of graph traversal, which we will revisit when discussing graph algorithms.

Expanding DFS and BFS into Specific Traversal Types

Depth-First Traversal (DFS)

  • Pre-order Traversal (Recursive, Iterative)
  • In-order Traversal (Recursive, Iterative)
  • Post-order Traversal (Recursive, Iterative)

Breadth-First Traversal (BFS)

  • Level-Order Traversal (Iterative)

A Simple Trick to Differentiate Preorder, In-order, and Post-order

Many people struggle to distinguish between preorder, in order, and post order traversals. A simple rule to remember:

The terms "pre," "in," and "post" refer to the order in which the root (middle) node is processed.

If you look at the root node's position relative to the left and right children, you can easily determine the traversal type:

  • Pre-order Traversal: Root → Left → Right (Root comes first)
  • In-order Traversal: Left → Root → Right (Root is in the middle)
  • Post-order Traversal: Left → Right → Root (Root comes last)

Refer to the following illustration to check if your understanding of pre-order, in-order, and post-order traversal is correct.

  graph TD

    %% Tree structure
    N5((5)) --> N4((4))
    N5 --> N6((6))
    N4 --> N1((1))
    N4 --> N2((2))
    N6 --> N7((7))
    N6 --> N8((8))


    %% Styling
    classDef default fill:#F78B8B,stroke:#333,stroke-width:2px
    classDef text-node fill:none,stroke:none
    class Pre,In,Post text-node
  • Pre-order Traversal (Root → Left → Right): 5 → 4 → 1 → 2 → 6 → 7 → 8
  • In-order Traversal (Left → Root → Right): 1 → 4 → 2 → 5 → 7 → 6 → 8
  • Post-order Traversal (Left → Right → Root): 1 → 2 → 4 → 7 → 8 → 6 → 5

Finally, let's talk about the implementation methods of depth-first and breadth-first traversal in binary trees. When we tackle problems related to binary trees, we often use recursion to implement depth-first traversal, which includes pre-order, in-order, and post-order traversals; using recursion is quite convenient.

Previously, when discussing stacks and queues, we mentioned that a stack is essentially a structure that implements recursion. This means that the logic for pre-order, in-order, and post-order traversals can actually be implemented using a stack with recursion.

On the other hand, breadth-first traversal is generally implemented using a queue. This is determined by the first-in-first-out characteristic of queues because it requires such a structure to traverse the binary tree layer by layer.

Definition of a Binary Tree

Earlier, we discussed two storage methods for binary trees:

  1. Sequential Storage – Using an array (simple, but best for complete binary trees).
  2. Linked Storage – Using pointers (more flexible and commonly used).

Since sequential storage (array-based) is straightforward, there’s not much to define there.

Now, let's take a look at how to define a binary tree node using linked storage (pointer-based representation).

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

You’ll notice that the definition of a binary tree node is quite similar to that of a linked list. However, unlike a linked list, which has one pointer per node, a binary tree node has two pointers, one pointing to the left child and the other to the right child.

Important Note for Interviews

When defining a binary tree node, pay close attention to the syntax and structure.

In live coding interviews, interviewers may ask you to write the definition from scratch. Therefore, it is crucial to practice writing data structures and basic logic on paper.

On platforms like LeetCode, the node structure is often predefined, so many candidates get caught off guard when they have to write it themselves during an interview.

Summary

A binary tree is a fundamental data structure, frequently tested in algorithm interviews and serving as the foundation for many advanced data structures.

In this guide, we covered:
✅ Types of Binary Trees
✅ Storage Methods (Linked vs. Sequential)
✅ Traversal Techniques (DFS & BFS)
✅ Definition of a Binary Tree Node

This provides a comprehensive review of key binary tree concepts to strengthen your foundation.

A Final Thought: Mastering Recursion

When discussing binary trees, we must talk about recursion. Many people find recursion to be both familiar and confusing—the code is often short and elegant, but it’s easy to understand conceptually yet struggle when implementing it.

💡 "I can understand it when I see it, but I mess up when I write it!"

Mastering recursion is essential for working with binary trees effectively.
So, if you feel stuck, don’t worry—practice is key! 🚀

  1. Binary Tree Traversal Methods
  1. Binary Tree Properties
  1. Binary Tree Modification and Construction
  1. Binary Search Tree Properties
  1. Binary Tree Lowest Common Ancestor Problems

6.Binary Search Tree Modification and Construction