Binary Tree: Types, Structure and Basic Terminology

Introduction and Basics of Binary Trees

A binary tree is a hierarchical data structure in which every node can have at most two children:

• A left child

• A right child

Each node generally contains:

• Data – The value stored in the node

• Left reference – Connects the node to its left child

• Right reference – Connects the node to its right child

Unlike arrays, linked lists, stacks, and queues, a binary tree is not linear. Its elements form parent-child relationships across multiple levels.

Consider a binary tree containing the following relationships:

• Node 1 is the root.

• Nodes 2 and 3 are the children of 1.

• Nodes 4 and 5 are the children of 2.

• Node 6 is the right child of 3.

The left and right positions are distinct. A node with only a left child represents a different structure from a node with only a right child, even if both children store the same value.

Why Are Binary Trees Used?

Binary trees organize data through hierarchical relationships rather than a single sequential order.

They are useful when a problem requires:

• Representing hierarchical information

• Dividing a problem into two smaller subproblems

• Searching through ordered data

• Processing expressions

• Maintaining priority

• Representing recursive relationships

• Performing divide-and-conquer operations

Many important data structures are specialized forms of binary trees, including:

• Binary Search Trees

• Binary Heaps

• AVL Trees

• Red-Black Trees

• Segment Trees

• Syntax Trees

• Expression Trees

• Huffman Trees

Recursive Structure of a Binary Tree

A binary tree has a naturally recursive structure.

Every binary tree is either:

• Empty, represented by NULL, or

• A node containing a value, a left binary subtree, and a right binary subtree

The left and right children are themselves roots of smaller binary trees.

This makes recursion a natural way to process trees:

• Handle the current node.

• Recursively process the left subtree.

• Recursively process the right subtree.

• Stop when a NULL reference is reached.

The order of these actions determines the traversal being performed.

Basic Terminology

Consider the example tree described earlier.

Root, Parent, and Child

The root is the only node with no parent.

In the example:

• 1 is the root.

• 1 is the parent of 2 and 3.

• 2 is the left child of 1.

• 3 is the right child of 1.

• 4 and 5 are the children of 2.

Every node except the root has exactly one parent in a valid tree.

Leaf and Internal Nodes

A leaf node has no children.

In the example:

4, 5, and 6 are leaf nodes.

An internal node has at least one child.

In the example:

1, 2, and 3 are internal nodes.

A single-node tree contains only its root. Since that node has no children, it is also a leaf.

Ancestors and Descendants

If a node lies on the path from the root to another node, it is an ancestor of that node.

For node 5:

• 1 and 2 are its ancestors.

• 2 is its parent.

• 1 is an ancestor but not its direct parent.

A descendant is the reverse relationship.

For node 2:

• 4 and 5 are its descendants.

• Both are also its direct children.

A node is generally not considered its own ancestor or descendant unless a problem explicitly defines the relationship differently.

Subtree

Every node can be treated as the root of its own smaller tree.

The subtree rooted at node 2 contains:

2, 4, and 5

The subtree rooted at a leaf node contains only that leaf.

This recursive property is central to most binary-tree algorithms. A problem on the complete tree is frequently solved by first solving it for the left and right subtrees.

Depth and Level

The depth of a node is the number of edges from the root to that node.

Using zero-based depth:

• The root has depth 0.

• Its children have depth 1.

• Their children have depth 2.

The word level is sometimes used in the same way as depth. Some resources number the root as level 1 instead of level 0, so the convention should always be stated clearly.

In this article:

Level = Depth

and the root is at level 0.

Height of a Node and Tree

The height of a node is the number of edges on the longest path from that node to a leaf.

Using edge-based height:

• A leaf node has height 0.

• A node whose deepest leaf is one edge below has height 1.

• The height of the tree equals the height of its root.

For the example tree:

• Nodes 4, 5, and 6 have height 0.

• Nodes 2 and 3 have height 1.

• Node 1 has height 2.

Some implementations define height using the number of nodes instead of edges. Under that convention, every height is one greater. The chosen definition must be used consistently.

Degree of a Node

The degree of a node is its number of children.

In a binary tree, a node can have degree:

• 0 for no children

• 1 for one child

• 2 for two children

The maximum possible degree of a node in a binary tree is 2.

Important Properties of Binary Trees

Assume that the root is at level 0 and the height is measured in edges.

Number of Edges

A non-empty tree with N nodes contains:

N - 1 edges

Every node except the root has exactly one connection from its parent.

Maximum Nodes at a Level

The maximum number of nodes at level L is:

2ᴸ

For example:

• Level 0 can contain at most 1 node.

• Level 1 can contain at most 2 nodes.

• Level 2 can contain at most 4 nodes.

• Level 3 can contain at most 8 nodes.

Maximum Nodes for Height H

The maximum number of nodes in a binary tree of height H is:

2ᴴ⁺¹ - 1

This maximum is achieved by a perfect binary tree.

Minimum Nodes for Height H

The minimum number of nodes in a binary tree of height H is:

H + 1

This occurs when every internal node has only one child, forming a chain.

Leaves in a Perfect Binary Tree

A perfect binary tree of height H contains:

2ᴴ leaf nodes

Its total number of nodes is:

2ᴴ⁺¹ - 1

Types of Binary Trees

1. Full Binary Tree

A full binary tree, also called a strict or proper binary tree, is one in which every node has either:

• No children, or

• Exactly two children

No node has only one child.

2. Complete Binary Tree

A complete binary tree has:

• Every level completely filled except possibly the final level.

• Nodes in the final level placed as far left as possible.

Complete binary trees are well suited for array representation and are commonly used to implement binary heaps.

3. Perfect Binary Tree

A perfect binary tree has:

• Exactly two children for every internal node.

• All leaf nodes at the same level.

• Every level completely filled.

Every perfect binary tree is both full and complete.

However, a complete tree is not necessarily perfect, and a full tree is not necessarily complete.

4. Balanced Binary Tree

A binary tree is considered balanced when its height remains reasonably small compared with its number of nodes.

A common definition of a height-balanced tree requires that, for every node, the heights of its left and right subtrees differ by at most 1.

A balanced tree containing N nodes generally has height proportional to:

O(log N)

Balanced does not mean that every level must be completely filled.

5. Degenerate Binary Tree

A degenerate binary tree is one in which every internal node has only one child.

Its structure resembles a linked list.

For N nodes, its height becomes:

N - 1

Operations that depend on height may degrade from O(log N) to O(N).

6. Skewed Binary Tree

A skewed tree is a degenerate tree in which all nodes extend in the same direction.

It may be:

• Left-skewed

• Right-skewed

Every skewed tree is degenerate, but a degenerate tree may alternate between left and right children.

Binary Tree Representation

A binary tree is commonly represented in two ways:

1. Linked representation

2. Array representation

1. Linked Representation

In linked representation, every node stores:

• Its data

• A reference to its left child

• A reference to its right child

If a child does not exist, the corresponding reference stores NULL.

The tree is accessed using a reference to its root.

Advantages

• Nodes can be created when required.

• Sparse and irregular trees do not waste array positions.

• Child connections can be changed directly.

• It naturally represents most general binary trees.

Limitations

• Every node requires storage for two references.

• Nodes may not occupy contiguous memory.

• There is no direct index-based access to an arbitrary node.

2. Array Representation

In zero-based array representation, the root is stored at index 0.

For a node stored at index i:

Left Child Index = 2i + 1

Right Child Index = 2i + 2

For a non-root node:

Parent Index = floor((i - 1) / 2)

Consider:

[1, 2, 3, 4, 5, 6, 7]

The relationships are:

• Node 1 at index 0 has children 2 and 3.

• Node 2 at index 1 has children 4 and 5.

• Node 3 at index 2 has children 6 and 7.

Advantages

• Parent and child indices can be calculated directly.

• No explicit child references are required.

• It is efficient for complete or nearly complete trees.

• It provides good memory locality.

Limitations

• Sparse or skewed trees may leave many unused positions.

• Resizing may be required when the allocated capacity is exhausted.

• Structural changes can be less convenient than linked representation.

Binary Tree Traversals

Traversal means visiting every node of the tree exactly once in a defined order.

Binary-tree traversals are divided into:

• Depth-First Search

• Breadth-First Search

Consider the following relationships:

• Root 1

• Left child 2 and right child 3

• Children 4 and 5 under node 2

• Right child 6 under node 3

Depth-First Search

Depth-First Search explores one subtree deeply before moving to another subtree.

There are three primary DFS traversals.

Preorder Traversal

Order:

Root → Left → Right

For the example:

1, 2, 4, 5, 3, 6

Preorder is useful when the current node must be processed before its subtrees, such as while copying or serializing a tree.

Inorder Traversal

Order:

Left → Root → Right

For the example:

4, 2, 5, 1, 3, 6

Inorder traversal produces sorted values for a Binary Search Tree, but not necessarily for a general binary tree.

Postorder Traversal

Order:

Left → Right → Root

For the example:

4, 5, 2, 6, 3, 1

Postorder is useful when child subtrees must be processed before their parent, such as while deleting a tree or evaluating expression trees.

Breadth-First Search

Breadth-First Search visits nodes one level at a time from left to right. It is also called level-order traversal.

For the example:

1, 2, 3, 4, 5, 6

A queue is commonly used to preserve the order in which nodes must be processed.

Level-order traversal is useful for:

• Processing nodes by level

• Finding minimum-depth information

• Viewing the tree layer by layer

• Solving width and level-based problems

Traversal Complexity

Every complete traversal visits all N nodes.

Therefore:

Time Complexity: O(N)

The auxiliary space depends on the traversal.

Recursive DFS

Recursive DFS uses the call stack.

Space Complexity: O(H)

where H is the height of the tree.

• Balanced tree: O(log N)

• Skewed tree: O(N)

Iterative DFS

Iterative DFS uses an explicit stack.

Its worst-case auxiliary space is:

O(N)

The exact maximum depends on the shape of the tree and traversal method.

Level-Order Traversal

Level-order traversal uses a queue that may hold an entire level.

Space Complexity: O(W)

where W is the maximum width of the tree.

In the worst case:

W = O(N)

Basic Operation Complexities

A general binary tree does not impose any ordering rule on its values. Therefore, operations cannot automatically choose between the left and right subtrees based on the target.

Insertion and deletion do not have one universal complexity for a general binary tree because the location and structural rule depend on the specific problem.

Binary Tree and Binary Search Tree

A binary tree and a Binary Search Tree are not the same.

A Binary Search Tree is a special type of binary tree.

A balanced Binary Search Tree can support search, insertion, and deletion in O(log N) time. A skewed Binary Search Tree may require O(N) time.

Applications of Binary Trees

Binary trees are used in:

• Binary Search Trees for ordered data

• Binary Heaps for priority queues

• Expression trees for arithmetic expressions

• Syntax trees in compilers

• Huffman coding trees for compression

• Segment trees for range queries

• Decision trees in machine learning

• Game trees for decision-making

• Hierarchical state representation

Advantages of Binary Trees

• They naturally represent hierarchical relationships.

• Their recursive structure simplifies many algorithms.

• Specialized binary trees can provide efficient searching and updates.

• They support several useful traversal orders.

• They can grow dynamically in linked representation.

• They form the foundation of many advanced data structures.

Limitations of Binary Trees

• A general binary tree does not guarantee efficient searching.

• Every linked node requires additional child references.

• Poor insertion order may create a skewed structure.

• Recursive traversal can cause stack overflow for very deep trees.

• Sparse trees may waste space in array representation.

• More pointer management is required than in contiguous structures.

Common Mistakes

• Assuming every binary tree follows the Binary Search Tree ordering rule.

• Confusing complete, full, perfect, and balanced binary trees.

• Treating left and right children as interchangeable.

• Mixing node-based and edge-based height definitions.

• Forgetting that a single-node tree has height 0 under the edge-based definition.

• Assuming a balanced tree must be complete.

• Forgetting the base case for a NULL node during recursion.

• Calculating DFS space as O(N) without considering the tree height.

• Assuming inorder traversal of every binary tree is sorted.

• Using array representation for a highly sparse tree without considering wasted positions.

• Forgetting that a non-empty tree with N nodes has N - 1 edges.