Binary tree

// unordered binary tree

traversal

let t be a binary tree
a binary tree, t, has three access methods:
t.info    returns the data store at the node t
t.L       returns the left subtree of t
t.R       returns the right subtree of t

Visit every nodes of the tree

preorder t
if t != null
     print t.info
     preorder t.L
     preorder t.R

inorder t
if t != null
     inorder t.L
     print t.info
     inorder t.R

postorder t
if t != null
     postorder t.L
     postorder t.R
     print t.info

tree operations

Insert a node, x, into a binary tree, t
We do not worry about the relation between data yet. We just put x anywhere that is valid (t is still a tree).

insert x t
if t.L == null t.L = x
else if t.R == null t.R = x
else insert x t.L

Note: using the above program, the result tree will be quite balanced (left and right branch are almost equal).

Assume we want to delete every appearance of "a" in a tree.
Assume the tree has "a".
There are three cases:
1) the node that stores "a" does not have child.
2) the node that stores "a" have a child.
3) the node that stores "a" have two children.

To "update" the parent node successfully, you need to look "ahead" to its children.

case 1

detele a t
if a == t.L.info
     t.L = null        // delete it
delete a t.L
delete a t.R         // and do it everywhere

You put "a" child to its parent
case 2

delete a t
if a == t.L.info and t.L has only one child (d)
     t.L = d
delete a t.L
delete a t.R

The final case, with two children, one child will be given to its parent another one will be given to the "sibling".... (try to do it yourself).
What will happen if there is no "a" in the tree?    How to check if we have already visited all nodes?

Prabhas Chongstitvatana
last update 26 Mar 2010