Binary Trees
"A tree may grow a
thousand feet tall, but
its leaves will return to
its roots."
-Chinese Proverb
Definitions
A tree is an abstract data type root node
internal
– one entry point, the root nodes
– Each node is either a leaf or an
internal node
– An internal node has 1 or more
children, nodes that can be
reached directly from that
internal node.
– The internal node is said to be
the parent of its child nodes leaf nodes
CS314 Binary Trees 2
Properties of Trees
Only access point is the root
All nodes, except the root, have one parent
– like the inheritance hierarchy in Java
Traditionally trees drawn upside down
root
CS314 Binary Trees leaves 3
Properties of Trees and Nodes
siblings: two nodes that root
have the same parent edge
0
edge: the link from one
node to another 1 2
path length: the number of
edges that must be siblings
traversed to get from one 3
node to another
path length from root to this 4 5
node is 3
CS314 Binary Trees 4
More Properties of Trees
depth: the path length from the root of the tree
to this node
height of a node: The maximum distance
(path length) of any leaf from this node
– a leaf has a height of 0
– the height of a tree is the height of the root of that
tree
descendants: any nodes that can be reached
via 1 or more edges from this node
ancestors: any nodes for which this node is a
descendant
CS314 Binary Trees 5
Tree Visualization
A
B C D
E F G H I J
K L M
N O
CS314 Binary Trees 6
Binary Trees
There are many variations on trees but we
will start with binary trees
binary tree: each node has at most two
children
– the possible children are usually referred to as
the left child and the right child
parent
left child right child
CS314 Binary Trees 7
Full Binary Tree
full binary tree: a binary tree in which each
node has 2 or 0 children
CS314 Binary Trees 8
Complete Binary Tree
complete binary tree: a binary tree in which
every level, except possibly the deepest is
completely filled. At depth n, the height of the
tree, all nodes are as far left as possible
Where would the next node go
to maintain a complete tree?
CS314 Binary Trees 9
Perfect Binary Tree
perfect binary tree: a binary tree with all leaf
nodes at the same depth. All internal nodes
have exactly two children.
a perfect binary tree has the maximum
number of nodes for a given height
a perfect binary tree has (2(n+1) - 1) nodes
where n is the height of the tree
– height = 0 -> 1 node
– height = 1 -> 3 nodes
– height = 2 -> 7 nodes
– height = 3 -> 15 nodes
CS314 Binary Trees 10
Binary Tree Traversals
Many algorithms require all nodes of a binary tree
be visited and the contents of each node processed
or examined.
There are 4 traditional types of traversals
– preorder traversal: process the root, then process all sub
trees (left to right)
– in order traversal: process the left sub tree, process the
root, process the right sub tree
– post order traversal: process the left sub tree, process
the right sub tree, then process the root
– level order traversal: starting from the root of a tree,
process all nodes at the same depth from left to right,
then proceed to the nodes at the next depth.
CS314 Binary Trees 11
Results of Traversals
To determine the results of a traversal on a
given tree draw a path around the tree.
– start on the left side of the root and trace around
the tree. The path should stay close to the tree.
12 pre order: process when
pass down left side of node
12 49 13 5 42
49 42 in order: process when pass
underneath node
13 49 5 12 42
13 5 post order: process when
pass up right side of node
CS314 Binary Trees 13 5 49 42 12 12
What is a Binary Tree
• A binary tree is a a collection of nodes that
consists of the root and other subsets to the root
points, which are called the left and right subtrees.
• Every parent node on a binary tree can have up to
two child nodes (roots of the two subtrees); any
more children and it becomes a general tree.
• A node that has no children is called a leaf node.
A Few Terms Regarding Binary Trees
B C
D E F
A is the root
B and C are A’s children
A is B’s parent G
B & C are the root of two subtrees
D, E, and G are leaves
This is NOT A Binary Tree
B C
D E F G H
This is a general tree because C has three child nodes
This is NOT A Binary Tree
B C
D E F G
This is a graph H
because A, B, E, H, F and C
form a circuit
Tree Traversal
• There are three common ways to traverse a tree:
– Preorder: Visit the root, traverse the left subtree
(preorder) and then traverse the right subtree (preorder)
– Postorder: Traverse the left subtree (postorder),
traverse the right subtree (postorder) and then visit the
root.
– Inorder: Traverse the left subtree (in order), visit the
root and the traverse the right subtree (in order).
Tree Traversals
There are mainly three ways to traverse a tree:
1) Inorder Traversal
2) Postorder Traversal
3) Preorder Traversal
Inorder Traversal: A E H J M T Y
Visit second
tree
‘J’
‘E’ ‘T’
‘A’ ‘H’ ‘M’ ‘Y’
Visit left subtree first Visit right subtree last
19
Inorder Traversal
• Visit the nodes in the left subtree, then visit
the root of the tree, then visit the nodes in
the right subtree
Inorder(tree)
If tree is not NULL
Inorder(Left(tree))
Visit Info(tree)
Inorder(Right(tree))
Warning:
Warning "visit" implies do something with the value at
the node (e.g., print, save, update etc.).
Preorder Traversal: J E A H T M Y
Visit first
tree
‘J’
‘E’ ‘T’
‘A’ ‘H’ ‘M’ ‘Y’
Visit left subtree second Visit right subtree last
21
Preorder Traversal
• Visit the root of the tree first, then visit the
nodes in the left subtree, then visit the
nodes in the right subtree
Preorder(tree)
If tree is not NULL
Visit Info(tree)
Preorder(Left(tree))
Preorder(Right(tree))
Postorder Traversal: A H E M Y T J
Visit last
tree
‘J’
‘E’ ‘T’
‘A’ ‘H’ ‘M’ ‘Y’
Visit left subtree first Visit right subtree second
23
Postorder Traversal
• Visit the nodes in the left subtree first, then
visit the nodes in the right subtree, then visit
the root of the tree
Postorder(tree)
If tree is not NULL
Postorder(Left(tree))
Postorder(Right(tree))
Visit Info(tree)
Tree Traversals: An Example
A
B C
D E F
Preorder: ABDECFG
Postorder: DEBGFCA G
In Order: DBEAFGC
Tree Traversals: An Example
A
B C
D E F
Preorder: A
(visit each node as your reach it) G
Tree Traversals: An Example
A
B C
D E F
Preorder: AB
(visit each node as your reach it) G
Tree Traversals: An Example
A
B C
D E F
Preorder: ABD
(visit each node as your reach it) G
Tree Traversals: An Example
A
B C
D E F
Preorder: ABDE
(visit each node as your reach it) G
Tree Traversals: An Example
A
B C
D E F
Preorder: ABDEC
(visit each node as your reach it) G
Tree Traversals: An Example
A
B C
D E F
Preorder: ABDECF
(visit each node as your reach it) G
Tree Traversals: An Example
A
B C
D E F
Preorder: ABDECFG
(visit each node as your reach it) G
Tree Traversals: An Example
A
B C
D E F
Postorder:
G
Tree Traversals: An Example
A
B C
D E F
Postorder:
G
Tree Traversals: An Example
A
B C
D E F
Postorder: D
G
Tree Traversals: An Example
A
B C
D E F
Postorder: DE
G
Tree Traversals: An Example
A
B C
D E F
Postorder: DEB
G
Tree Traversals: An Example
A
B C
D E F
Postorder: DEB
G
Tree Traversals: An Example
A
B C
D E F
Postorder: DEB
G
Tree Traversals: An Example
A
B C
D E F
Postorder: DEBG
G
Tree Traversals: An Example
A
B C
D E F
Postorder: DEBGF
G
Tree Traversals: An Example
A
B C
D E F
Postorder: DEBGFC
G
Tree Traversals: An Example
A
B C
D E F
Postorder: DEBGFCA
G
Tree Traversals: An Example
A
B C
D E F
G
In Order:
Tree Traversals: An Example
A
B C
D E F
G
In Order:
Tree Traversals: An Example
A
B C
D E F
G
In Order: D
Tree Traversals: An Example
A
B C
D E F
G
In Order: DB
Tree Traversals: An Example
A
B C
D E F
G
In Order: DBE
Tree Traversals: An Example
A
B C
D E F
G
In Order: DBEA
Tree Traversals: An Example
A
B C
D E F
G
In Order: DBEA
Tree Traversals: An Example
A
B C
D E F
G
In Order: DBEAF
Tree Traversals: An Example
A
B C
D E F
G
In Order: DBEAFG
Tree Traversals: An Example
A
B C
D E F
G
In Order: DBEAFGC
Tree Traversals: An Example
A
B C
D E F
Preorder: ABDECFG
Postorder: DEBGFCA G
In Order: DBEAFGC
Tree Traversals: Another Example
A
B C
D E
G
F
Preorder: ABDFHIECG
Postorder: HIFDEBGCA
H I In Order: DHFIBEACG
Tree Traversals: Another Example
A
B C
D E
G
F
Preorder: A
H I
Tree Traversals: Another Example
A
B C
D E
G
F
Preorder: AB
H I
Tree Traversals: Another Example
A
B C
D E
G
F
Preorder: ABD
H I
Tree Traversals: Another Example
A
B C
D E
G
F
Preorder: ABDF
H I
Tree Traversals: Another Example
A
B C
D E
G
F
Preorder: ABDFH
H I
Tree Traversals: Another Example
A
B C
D E
G
F
Preorder: ABDFHI
H I
Tree Traversals: Another Example
A
B C
D E
G
F
Preorder: ABDFHIE
H I
Tree Traversals: Another Example
A
B C
D E
G
F
Preorder: ABDFHIEC
H I
Tree Traversals: Another Example
A
B C
D E
G
F
Preorder: ABDFHIECG
H I
Tree Traversals: Another Example
A
B C
D E
G
Postorder:
H I
Tree Traversals: Another Example
A
B C
D E
G
Postorder:
H I
Tree Traversals: Another Example
A
B C
D E
G
Postorder:
H I
Tree Traversals: Another Example
A
B C
D E
G
Postorder:
H I
Tree Traversals: Another Example
A
B C
D E
G
Postorder: H
H I
Tree Traversals: Another Example
A
B C
D E
G
Postorder: HI
H I
Tree Traversals: Another Example
A
B C
D E
G
Postorder: HIF
H I
Tree Traversals: Another Example
A
B C
D E
G
Postorder: HIFD
H I
Tree Traversals: Another Example
A
B C
D E
G
Postorder: HIFDE
H I
Tree Traversals: Another Example
A
B C
D E
G
Postorder: HIFDEB
H I
Tree Traversals: Another Example
A
B C
D E
G
Postorder: HIFDEB
H I
Tree Traversals: Another Example
A
B C
D E
G
Postorder: HIFDEBG
H I
Tree Traversals: Another Example
A
B C
D E
G
Postorder: HIFDEBGC
H I
Tree Traversals: Another Example
A
B C
D E
G
Postorder: HIFDEBGCA
H I
Tree Traversals: Another Example
A
B C
D E
G
H I In Order:
Tree Traversals: Another Example
A
B C
D E
G
H I In Order:
Tree Traversals: Another Example
A
B C
D E
G
H I In Order: D
Tree Traversals: Another Example
A
B C
D E
G
H I In Order: D
Tree Traversals: Another Example
A
B C
D E
G
H I In Order: DH
Tree Traversals: Another Example
A
B C
D E
G
H I In Order: DHF
Tree Traversals: Another Example
A
B C
D E
G
H I In Order: DHFI
Tree Traversals: Another Example
A
B C
D E
G
H I In Order: DHFIB
Tree Traversals: Another Example
A
B C
D E
G
H I In Order: DHFIBE
Tree Traversals: Another Example
A
B C
D E
G
H I In Order: DHFIBEA
Tree Traversals: Another Example
A
B C
D E
G
H I In Order: DHFIBEAC
Tree Traversals: Another Example
A
B C
D E
G
H I In Order: DHFIBEACG
Tree Traversals: Another Example
A
B C
D E
G
F
Preorder: ABDFHIECG
Postorder: HIFDEBGCA
H I In Order: DHFIBEACG
Basic Implementation of a Binary
Tree
• We can implement a binary in essentially
the same way as a linked list, except that
there are two nodes that comes next:
public class Node {
private int data;
private Node left;
private Node right;
public int getData() {
return data;
}
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
public void setData(int x) {
data = x;
}
public void setLeft(Node p) {
left = p;
}
public void setRight(Node p) {
right = p;
}
}
The tree Class
public class Tree {
private Node root;
// tree() - The default constructor – Starts
// the tree as empty
public Tree() {
root = null;
}
// Tree() - An initializing constructor that
// creates a node and places in it
// the initial value
public Tree(int x) {
root = new Node();
root.setData(x);
root.setLeft(null);
root.setRight(null);
}
public Node getRoot() {
return root;
}
// newNode() - Creates a new node with a
// zero as data by default
public Node newNode() {
Node p = new Node();
p.setData(0);
p.setLeft(null);
p.setRight(null);
return(p);
}
// newNode() - Creates a new node with the
// parameter x as its value
public Node newNode(int x) {
Node p = new Node();
p.setData(x);
p.setLeft(null);
p.setRight(null);
return(p);
}
//travTree() – initializes recursive
// traversal of tree
public void travTree() {
if (root != null)
travSubtree(root);
System.out.println();
}
//travSubtree() – recursive method used to
// traverse a binary tree (inorder)
public void travSubtree(Node p) {
if (p != null) {
travSubtree(p.getLeft());
System.out.print(p.getData()
+ "\t");
travSubtree(p.getRight());
}
}
// addLeft() - Inserts a new node containing
// x as the left child of p
public void addLeft(Node p, int x) {
Node q = newNode(x);
p.setLeft(q);
}
// addRight() - Inserts a new node containing
// x as the right child of p
public void addRight(Node p, int x) {
Node q = newNode(x);
p.setRight(q);
}
}
A Basic Search Tree
• We can construct a simple search tree if we
add new nodes with value x on the tree
using this strategy:
– Every time x is less than the value in the node
we move down to the left.
– Every time x is greater than the value in the
node we move down to the right.
A Sample Search Tree
15
8 22
5 12 18 23
7 10 16 20
// insert() - Insert value x in a new node
to
// be inserted after p
public void insert(int x) {
Node p, q;
boolean found = false;
p = root;
q = null;
while (p != null && !found) {
q = p;
if (p.getData() == x)
found = true;
else if (p.getData() > x)
p = p.getLeft();
else
p = p.getRight();
}
if (found)
error("Duplicate entry");
if (q.getData() > x)
addLeft(q, x);
else
addRight(q, x);
//q = newNode(x);
}
// isXThere() - Is there a node in the
// tree containing x?
public boolean isXThere(int x) {
Node p;
boolean found = false;
p = root;
while (p != null && !found) {
if (p.getData() == x)
found = true;
else if (p.getData() > x)
p = p.getLeft();
else
p = p.getRight();
}
return(found);
}
public void error(String message) {
System.out.println(message);
System.exit(0);
}
// getNode() - Get the pointer for the
// node containing x
public Node getNode(int x) {
Node p, q;
boolean found = false;
p = root;
q = null;
while (p != null && !found) {
q = p;
if (p.getData() == x)
found = true;
else if (p.getData() > x)
p = p.getLeft();
else
p = p.getRight();
}
if (found)
return(q);
else
return(null);
}
public class TestTree {
public static void main(String[] args) {
Tree mytree = new Tree(8);
mytree.addLeft(mytree.getRoot(), 6);
mytree.addRight(mytree.getRoot(), 9);
mytree.insert(4);
mytree.insert(1);
mytree.insert(12);
if (mytree.isXThere(13))
System.out.println("great");
else
System.out.println("not great, Bob");
mytree.travTree();
}
}
Tracing TestTree
8
Tracing TestTree
8
6
Tracing TestTree
8
6
9
Tracing TestTree
8
6
9
4
Tracing TestTree
8
6
9
1
Tracing TestTree
8
6
9
4 12
