Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Binary Trees

Binary Trees
by Nick Parlante
This article introduces the basic concepts of binary trees, and then works through a series of practice problems with
solution code in C/C++ and Java
...


Contents
Section 1
...
Binary Tree Problems -- practice problems in increasing order of difficulty
Section 3
...
Java versions -- how binary trees work in Java, with solution code

Stanford CS Education Library -- #110
This is article #110 in the Stanford CS Education Library
...
stanford
...
That people seeking education should have the opportunity to find it
...
Copyright
2000-2001, Nick Parlante, nick
...
stanford
...


Related CSLibrary Articles
Linked List Problems (http://cslibrary
...
edu/105/) -- a large collection of linked list problems
using various pointer techniques (while this binary tree article concentrates on recursion)
Pointer and Memory (http://cslibrary
...
edu/102/) -- basic concepts of pointers and memory
The Great Tree-List Problem (http://cslibrary
...
edu/109/) -- a great pointer recursion problem
that uses both trees and lists

Section 1 -- Introduction To Binary Trees
A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element
...
The left and right pointers recursively point to smaller
"subtrees" on either side
...
The formal
recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node,
where the left and right pointers (recursive definition ahead) each point to a binary tree
...
stanford
...
html

Page: 1

Binary Trees

Page: 2

A "binary search tree" (BST) or "ordered binary tree" is a type of binary tree where the nodes are arranged in order:
for each node, all elements in its left subtree are less-or-equal to the node (<=), and all the elements in its right
subtree are greater than the node (>)
...
Recursively, each of the subtrees must
also obey the binary search tree constraint: in the (1, 3, 4) subtree, the 3 is the root, the 1 <= 3 and 4 > 3
...

The nodes at the bottom edge of the tree have empty subtrees and are called "leaf" nodes (1, 4, 6) while the others
are "internal" nodes (3, 5, 9)
...
The next section presents the code for these two
algorithms
...
Therefore, binary search trees are good for "dictionary" problems where the code inserts and looks up
information indexed by some key
...


Strategy
Some of the problems in this article use plain binary trees, and some use binary search trees
...
(See the articles linked above for pointer articles
that do not emphasize recursion
...

The node/pointer structure that makes up the tree and the code that manipulates it
The algorithm, typically recursive, that iterates over the tree
When thinking about a binary tree problem, it's often a good idea to draw a few little trees to think about the
various cases
...
stanford
...
html

Binary Trees

Typical Binary Tree Code in C/C++
As an introduction, we'll look at the code for the two most basic binary search tree operations -- lookup() and
insert()
...
Java programers can read the discussion here, and then look at the Java
versions in Section 4
...

struct node {
int data;
struct node* left;
struct node* right;
}

Lookup()
Given a binary search tree and a "target" value, search the tree to see if it contains the target
...
If the tree is a binary search tree, there is
often some sort of less-than test on the node to decide if the recursion should go left or right
...
Recurs
down the tree, chooses the left or right
branch by comparing the target to each node
...
Base case == empty tree
// in that case, the target is not found so return false
if (node == NULL) {
return(false);
}
else {
// 2
...
otherwise recur down the correct subtree
if (target < node->data) return(lookup(node->left, target));
else return(lookup(node->right, target));
}
}
}

The lookup() algorithm could be written as a while-loop that iterates down the tree
...


Pointer Changing Code
There is a common problem with pointer intensive code: what if a function needs to change one of the pointer
parameters passed to it? For example, the insert() function below may want to change the root pointer
...
That's a fine technique, but here we will
use the simpler technique that a function that wishes to change a pointer passed to it will return the new value of
the pointer to the caller
...
Suppose we have a change() function
http://cslibrary
...
edu/110/
BinaryTrees
...

// suppose the variable "root" points to the tree
root = change(root);
We take the value returned by change(), and use it as the new value for root
...
This allows us to focus on the recursion instead of the pointer mechanics
...
stanford
...


Insert()
Insert() -- given a binary search tree and a number, insert a new node with the given number into the tree in the
correct place
...

As described above, insert() returns the new tree pointer to use to its caller
...

2
/ \
1

10

returns the tree
...
The base-case/recursion
structure is similar to the structure in lookup() -- each call checks for the NULL case, looks at the node at hand, and
then recurs down the left or right subtree if needed
...

*/
struct node* NewNode(int data) {
struct node* node = new(struct node);
// "new" is like "malloc"
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}

/*
Give a binary search tree and a number, inserts a new node
with the given number in the correct place in the tree
...

*/
struct node* insert(struct node* node, int data) {
http://cslibrary
...
edu/110/
BinaryTrees
...
If the tree is empty, return a new, single node
if (node == NULL) {
return(newNode(data));
}
else {
// 2
...
In particular, if the nodes
are inserted in increasing order (1, 2, 3, 4), the tree nodes just grow to the right leading to a linked list shape where
all the left pointers are NULL
...
The
linked list shape defeats the lg(N) performance
...


Section 2 -- Binary Tree Problems
Here are 14 binary tree problems in increasing order of difficulty
...
The next
section, Section 3, shows the solution code in C/C++
...
The
basic structure and recursion of the solution code is the same in both languages -- the differences are superficial
...
To get the most out of these problems, you should at least
attempt to solve them before looking at the solution
...
With any pointer-based code, it's a good idea to make memory drawings of a a few simple cases to
see how the algorithm should work
...
build123()
This is a very basic problem with a little pointer manipulation
...
) Write code that builds the following little 1-2-3 binary search tree
...

a: by calling newNode() three times, and using three pointer variables
b: by calling newNode() three times, and using only one pointer variable
c: by calling insert() three times passing it the root pointer to build up the tree
(In Java, write a build123() method that operates on the receiver to change it to be the 1-2-3 tree with the given
coding constraints
...
)
struct node* build123() {

2
...
stanford
...
html

Binary Trees

This problem demonstrates simple binary tree traversal
...

int size(struct node* node) {

3
...
The maxDepth of the empty tree is 0, the maxDepth of the tree on the first page is 3
...
minValue()
Given a non-empty binary search tree (an ordered binary tree), return the minimum data value found in that tree
...
A maxValue() function is structurally very similar to this
function
...

int minValue(struct node* node) {

5
...
So the tree
...
This is known as an "inorder" traversal of the tree
...

void printTree(struct node* node) {

6
...
So the tree
...
The description is complex, but the code is simple
...

http://cslibrary
...
edu/110/
BinaryTrees
...
hasPathSum()
We'll define a "root-to-leaf path" to be a sequence of nodes in a tree starting with the root node and proceeding
downward to a leaf (a node with no children)
...
So for
example, the following tree has exactly four root-to-leaf paths:
5
/ \
4

8
/ \
13 4

/
11
/

\

7

\
2

1

Root-to-leaf paths:
path 1: 5 4 11 7
path 2: 5 4 11 2
path 3: 5 8 13
path 4: 5 8 4 1
For this problem, we will be concerned with the sum of the values of such a path -- for example, the sum of the
values on the 5-4-11-7 path is 5 + 4 + 11 + 7 = 27
...
Return false if no such path can be found
...
)
int hasPathSum(struct node* node, int sum) {

8
...
This problem is a little harder than it
looks, since the "path so far" needs to be communicated between the recursive calls
...
Alternately, the problem
may be solved bottom-up, with each node returning its list of paths
...
(Thanks to Matthias Felleisen for suggesting this problem
...

void printPaths(struct node* node) {

9
...

So the tree
...
stanford
...
html

Page: 7

Binary Trees

1

Page: 8

3

is changed to
...
As it happens, this can be accomplished without changing the root node
pointer, so the return-the-new-root construct is not necessary
...

void mirror(struct node* node) {

10
...
The resulting tree should still be a binary search tree
...

2
/ \
1
3
is changed to
...

void doubleTree(struct node* node) {

11
...
(Thanks to Julie Zelenski for suggesting this problem
...
countTrees()
This is not a binary tree programming problem in the ordinary sense -- it's more of a math/combinatorics recursion
problem that happens to use binary trees
...
)
Suppose you are building an N node binary search tree with the values 1
...
How many structurally different
binary search trees are there that store those values? Write a recursive function that, given the number of distinct
values, computes the number of structurally unique binary search trees that store those values
...
stanford
...
html

Binary Trees

Page: 9

countTrees(4) should return 14, since there are 14 structurally unique binary search trees that store 1, 2, 3, and 4
...
Your code should not construct any actual trees; it's just a
counting problem
...
To be a binary search tree, for every node, all of the nodes in its
left tree must be <= the node, and all of the nodes in its right subtree must be > the node
...

a
...


7

5
/ \
6

-> FALSE, because the 6 is not ok to the left of the 5

c
...


5 -> FALSE, the 6 is ok with the 2, but the 6 is not ok with the 5
/ \
2
7
/ \
1
6

For the first two cases, the right answer can be seen just by comparing each node to the two nodes immediately
below it
...


13 isBST() -- version 1
Suppose you have helper functions minValue() and maxValue() that return the min or max int value from a
non-empty tree (see problem 3 above)
...
Use the helper functions, and don't forget to check every node in the tree
...
(Thanks to Owen Astrachan for the idea of having this problem, and comparing it to
problem 14)
Returns true if a binary tree is a binary search tree
...
isBST() -- version 2
http://cslibrary
...
edu/110/
BinaryTrees
...
A better solution looks at each
node only once
...
The initial values for min and max should be INT_MIN and INT_MAX -- they narrow from there
...

*/
int isBST2(struct node* node) {
return(isBSTRecur(node, INT_MIN, INT_MAX));
}
/*
Returns true if the given tree is a BST and its
values are >= min and <= max
...
Tree-List
The Tree-List problem is one of the greatest recursive pointer problems ever devised, and it happens to use binary
trees as well
...
stanford
...
The problem requires an understanding of binary trees, linked lists,
recursion, and pointers
...


Section 3 -- C/C++ Solutions
Make an attempt to solve each problem before looking at the solution -- it's the best way to learn
...
Build123() Solution (C/C++)
// call newNode() three times
struct node* build123a() {
struct node* root = newNode(2);
struct node* lChild = newNode(1);
struct node* rChild = newNode(3);
root->left = lChild;
root->right= rChild;
return(root);
}
// call newNode() three times, and use only one local variable
struct node* build123b() {
struct node* root = newNode(2);
root->left = newNode(1);
root->right = newNode(3);
return(root);
}
http://cslibrary
...
edu/110/
BinaryTrees
...

Note that the '2' must be inserted first
...
size() Solution (C/C++)
/*
Compute the number of nodes in a tree
...
maxDepth() Solution (C/C++)
/*
Compute the "maxDepth" of a tree -- the number of nodes along
the longest path from the root node down to the farthest leaf node
...
minValue() Solution (C/C++)
/*
Given a non-empty binary search tree,
return the minimum data value found in that tree
...
stanford
...
html

Page: 11

Binary Trees

Note that the entire tree does not need to be searched
...
printTree() Solution (C/C++)
/*
Given a binary search tree, print out
its data elements in increasing
sorted order
...
printPostorder() Solution (C/C++)
/*
Given a binary tree, print its
nodes according to the "bottom-up"
postorder traversal
...
hasPathSum() Solution (C/C++)
/*
Given a tree and a sum, return true if there is a path from the root
down to a leaf, such that adding up all the values along the path
equals the given sum
...
stanford
...
html

Page: 12

Binary Trees

Strategy: subtract the node value from the sum when recurring down,
and check to see if the sum is 0 when you run out of tree
...
printPaths() Solution (C/C++)
/*
Given a binary tree, print out all of its root-to-leaf
paths, one per line
...

*/
void printPaths(struct node* node) {
int path[1000];
printPathsRecur(node, path, 0);
}
/*
Recursive helper function -- given a node, and an array containing
the path from the root node up to but not including this node,
print out all the root-leaf paths
...

void printArray(int ints[], int len) {
int i;
for (i=0; ihttp://cslibrary
...
edu/110/
BinaryTrees
...
mirror() Solution (C/C++)
/*
Change a tree so that the roles of the
left and right pointers are swapped at every node
...

4
/ \
2
5
/ \
1
3
is changed to
...
doubleTree() Solution (C/C++)
/*
For each node in a binary search tree,
create a new duplicate node, and insert
the duplicate as the left child of the original node
...

So the tree
...
stanford
...
html

Page: 14

Binary Trees

1

3

Is changed to
...
sameTree() Solution (C/C++)
/*
Given two trees, return true if they are
structurally identical
...
both empty -> true
if (a==NULL && b==NULL) return(true);
// 2
...
one empty, one not -> false
else return(false);
}

12
...
numKeys, how many structurally unique
http://cslibrary
...
edu/110/
BinaryTrees
...

Strategy: consider that each value could be the root
...

*/
int countTrees(int numKeys) {
if (numKeys <=1) {
return(1);
}
else {
// there will be one value at the root, with whatever remains
// on the left and right each forming their own subtrees
...

int sum = 0;
int left, right, root;
for (root=1; root<=numKeys; root++) {
left = countTrees(root - 1);
right = countTrees(numKeys - root);
// number of possible trees with this root == left*right
sum += left*right;
}
return(sum);
}
}

13
...

*/
int isBST(struct node* node) {
if (node==NULL) return(true);
// false if the min of the left is > than us
if (node->left!=NULL && minValue(node->left) > node->data)
return(false);
// false if the max of the right is <= than us
if (node->right!=NULL && maxValue(node->right) <= node->data)
return(false);
// false if, recursively, the left or right is not a BST
if (!isBST(node->left) || !isBST(node->right))
return(false);
// passing all that, it's a BST
return(true);
}

http://cslibrary
...
edu/110/
BinaryTrees
...
isBST2() Solution (C/C++)
/*
Returns true if the given tree is a binary search tree
(efficient version)
...

*/
int isBSTUtil(struct node* node, int min, int max) {
if (node==NULL) return(true);
// false if this node violates the min/max constraint
if (node->datadata>max) return(false);
// otherwise check the subtrees recursively,
// tightening the min or max constraint
return
isBSTUtil(node->left, min, node->data) &&
isBSTUtil(node->right, node->data+1, max)
);
}

15
...
stanford
...
In fact, I created the Java solutions by
just copying the C solutions, and then making the syntactic changes
...

In Java, we will have a BinaryTree object that contains a single root pointer
...
The Node class is private -- it is used only
for internal storage inside the BinaryTree and is not exposed to clients
...
For the lookup() operation, there is a BinaryTree
...
Internal to the BinaryTree class, there is a private recursive
lookup(Node) method that implements the recursion down the Node structure
...


Java Binary Tree Structure
To get started, here are the basic definitions for the Java BinaryTree class, and the lookup() and insert() methods
as examples
...
stanford
...
html

Binary Trees

// BinaryTree
...
Will be null for an empty tree
...

Each node stores one data element, and has left and right
sub-tree pointer which may be null
...

*/
private static class Node {
Node left;
Node right;
int data;
Node(int newData) {
left = null;
right = null;
data = newData;
}
}
/**
Creates an empty binary tree -- a null root pointer
...

Uses a recursive helper
...

*/
private boolean lookup(Node node, int data) {
if (node==null) {
return(false);
}
if (data==node
...
data) {
http://cslibrary
...
edu/110/
BinaryTrees
...
left, data));
}
else {
return(lookup(node
...

Uses a recursive helper
...
Returns the new
node pointer (the standard way to communicate
a changed pointer back to the caller)
...
data) {
node
...
left, data);
}
else {
node
...
right, data);
}
}
return(node); // in any case, return the new pointer to the caller
}

OOP Style vs
...
Internally, the Node class
and the recursive methods do not demonstrate OOP style
...
In particular, they do not operate against a
"receiver" in any special way
...
My sense is that the OOP style and the recursive style do not be combined
nicely for binary trees, so I have left them separate
...
It's possible to get around that by having
a special object to represent the null tree, but that seems like a distraction to me
...


Java Solutions
Here are the Java solutions to the 14 binary tree problems
...
stanford
...
html

Binary Trees

method that starts the computation, and a recursive method that does the real operation
...


1
...

void build123a() {
= new Node(2);
lChild = new Node(1);
rChild = new Node(3);

root
...
right= rChild;
}
/**
Build 123 using only one pointer variable
...
left = new Node(1);
root
...

Note that the '2' must be inserted first
...
size() Solution (Java)
/**
Returns the number of nodes in the tree
...

*/
public int size() {
return(size(root));
}
private int size(Node node) {
if (node == null) return(0);
else {
return(size(node
...
right));
}
}
http://cslibrary
...
edu/110/
BinaryTrees
...
maxDepth() Solution (Java)
/**
Returns the max root-to-leaf depth of the tree
...

*/
public int maxDepth() {
return(maxDepth(root));
}
private int maxDepth(Node node) {
if (node==null) {
return(0);
}
else {
int lDepth = maxDepth(node
...
right);
// use the larger + 1
return(Math
...
minValue() Solution (Java)
/**
Returns the min value in a non-empty binary search tree
...

*/
public int minValue() {
return( minValue(root) );
}

/**
Finds the min value in a non-empty binary search tree
...
left != null) {
current = current
...
data);
}

5
...

Uses a recursive helper to do the traversal
...
stanford
...
html

Page: 21

Binary Trees

*/
public void printTree() {
printTree(root);
System
...
println();
}
private void printTree(Node node) {
if (node == null) return;
// left, node itself, right
printTree(node
...
out
...
data + "
printTree(node
...
printPostorder() Solution (Java)
/**
Prints the node values in the "postorder" order
...

*/
public void printPostorder() {
printPostorder(root);
System
...
println();
}
public void printPostorder(Node node) {
if (node == null) return;
// first recur on both subtrees
printPostorder(node
...
right);
// then deal with the node
System
...
print(node
...
hasPathSum() Solution (Java)
/**
Given a tree and a sum, returns true if there is a path from the root
down to a leaf, such that adding up all the values along the path
equals the given sum
...

*/
public boolean hasPathSum(int sum) {
return( hasPathSum(root, sum) );
}
boolean hasPathSum(Node node, int sum) {
// return true if we run out of tree and sum==0
if (node == null) {
http://cslibrary
...
edu/110/
BinaryTrees
...
data;
return(hasPathSum(node
...
right, subSum));
}
}

8
...
Uses a recursive helper to do the work
...

*/
private void printPaths(Node node, int[] path, int pathLen) {
if (node==null) return;
// append this node to the path array
path[pathLen] = node
...
left==null && node
...
left, path, pathLen);
printPaths(node
...

*/
private void printArray(int[] ints, int len) {
int i;
for (i=0; iSystem
...
print(ints[i] + " ");
}
System
...
println();
}

http://cslibrary
...
edu/110/
BinaryTrees
...
mirror() Solution (Java)
/**
Changes the tree into its mirror image
...

4
/ \
2
5
/ \
1
3
is changed to
...

*/
public void mirror() {
mirror(root);
}
private void mirror(Node node) {
if (node != null) {
// do the sub-trees
mirror(node
...
right);
// swap the left/right pointers
Node temp = node
...
left = node
...
right = temp;
}
}

10
...
left
...

2
/ \
1
3
Is changed to
...
stanford
...
html

Page: 24

Binary Trees

/ \
2

3

/
1

/
3

/
1
Uses a recursive helper to recur over the tree
and insert the duplicates
...
left);
doubleTree(node
...
left;
node
...
data);
node
...
left = oldLeft;
}

11
...

*/
public boolean sameTree(BinaryTree other) {
return( sameTree(root, other
...

*/
boolean sameTree(Node a, Node b) {
// 1
...
both non-empty -> compare them
else if (a!=null && b!=null) {
return(
a
...
data &&
sameTree(a
...
left) &&
sameTree(a
...
right)
);
}
http://cslibrary
...
edu/110/
BinaryTrees
...
one empty, one not -> false
else return(false);
}

12
...
numKeys, how many structurally unique
binary search trees are possible that store those keys?
Strategy: consider that each value could be the root
...

*/
public static int countTrees(int numKeys) {
if (numKeys <=1) {
return(1);
}
else {
// there will be one value at the root, with whatever remains
// on the left and right each forming their own subtrees
...

int sum = 0;
int left, right, root;
for (root=1; root<=numKeys; root++) {
left = countTrees(root-1);
right = countTrees(numKeys - root);
// number of possible trees with this root == left*right
sum += left*right;
}
return(sum);
}
}

13
...

*/
public boolean isBST() {
return(isBST(root));
}
/**
Recursive helper -- checks if a tree is a BST
using minValue() and maxValue() (not efficient)
...
stanford
...
html

Page: 26

Binary Trees

// agree with the node?
if (node
...
left) > node
...
right!=null && minValue(node
...
data) return(false);
// check that the subtrees themselves are ok
return( isBST(node
...
right) );
}

14
...
Uses the efficient
recursive helper
...
MIN_VALUE, Integer
...
max range
...

*/
private boolean isBST2(Node node, int min, int max) {
if (node==null) {
return(true);
}
else {
// left should be in range min
...
data
boolean leftOk = isBST2(node
...
data);
// if the left is not ok, bail out
if (!leftOk) return(false);
// right should be in range node
...
max
boolean rightOk = isBST2(node
...
data+1, max);
return(rightOk);
}
}

http://cslibrary
...
edu/110/
BinaryTrees

---

Title: Binary trees
Description: It has an indepth understanding of Binary treesfrom scratch in C programming.

Buy These NotesPreview