Binary Tree Properties & Representation

Minimum Number Of Nodes

Minimum number of nodes in a binary tree
whose height is h.
At least one node at each of first h levels.

minimum number of
nodes is h

Maximum Number Of Nodes

All possible nodes at first h levels are present.
Number Of Nodes & Height

Let n be the number of nodes in a binary

tree whose height is h.
h <= n <= 2h 1
log2(n+1) <= h <= n

Maximum number of nodes

= 1 + 2 + 4 + 8 + + 2h-1
= 2h - 1
 Numbering Nodes In A Full Binary
Full Binary Tree
Tree
A full binary tree of a given height h has 2h 1 Number the nodes 1 through 2h 1.
nodes. Number by levels from top to bottom.
Within a level number from left to right.
1

2 3

4 5 6 7

Height 4 full binary tree. 8 9 10 11 12 13 14 15

Node Number Properties Node Number Properties

1 1

2 3 2 3

4 5 6 7 4 5 6 7
8 9 10 11 12 13 14 15 8 9 10 11 12 13 14 15

Parent of node i is node i / 2, unless i = 1. Left child of node i is node 2i, unless 2i > n,
Node 1 is the root and has no parent. where n is the number of nodes.
If 2i > n, node i has no left child.
 Node Number Properties Complete Binary Tree With n Nodes
1

2 3 Start with a full binary tree that has at least

n nodes.
4 5 6 7 Number the nodes as described earlier.
8 9 10 11 12 13 14 15 The binary tree defined by the nodes
numbered 1 through n is the unique n node
Right child of node i is node 2i+1, unless 2i+1 complete binary tree.
> n, where n is the number of nodes.
If 2i+1 > n, node i has no right child.

Example Binary Tree Representation

1

Array representation.
2 3
Linked representation.
4 5 6 7
8 9 10 11 12 13 14 15

Complete binary tree with 10 nodes.

 Array Representation Right-Skewed Binary Tree
Number the nodes using the numbering scheme a1
for a full binary tree. The node that is numbered b 3
i is stored in tree[i]. 7
c
a1
15
d
2 3
b c tree[] a - b - - - c - - - - - - - d
0 5 10 15
4 5 6 7
d e f g
8 9 10 An n node binary tree needs an array whose
h i j
length is between n+1 and 2n.
tree[] a b c d e f g h i j
0 5 10

Linked Representation The Class BinaryTreeNode

package dataStructures;
public class BinaryTreeNode
{
Each binary tree node is represented as an
object whose data type is BinaryTreeNode. Object element;
The space required by an n node binary tree BinaryTreeNode leftChild; // left subtree
is n * (space required by one node). BinaryTreeNode rightChild;// right subtree
// constructors and any other methods
// come here
}
 Linked Representation Example Some Binary Tree Operations
root a Determine the height.
Determine the number of nodes.
b c Make a clone.
Determine if two binary trees are clones.
d e Display the binary tree.
Evaluate the arithmetic expression
represented by a binary tree.
g
f Obtain the infix form of an expression.
leftChild
element h Obtain the prefix form of an expression.
rightChild Obtain the postfix form of an expression.

Binary Tree Traversal Binary Tree Traversal Methods

Many binary tree operations are done by
performing a traversal of the binary tree. Preorder
In a traversal, each element of the binary tree is Inorder
visited exactly once. Postorder
During the visit of an element, all action (make Level order
a clone, display, evaluate the operator, etc.)
with respect to this element is taken.