Binary Tree Traversal

Algorithm description

The following algorithm traverses a binary tree to find a node with a given key. This traversal can be used both in the insertion and in the seraching function.

Algorithm implementation

 1  function bintree_search (root: node_type; key: key_type) return node_type
 2  is
 3      node_pointer: node_type;
 4  
 5      function max_height_binary (N: natural) return natural
 6      is
 7      begin
 8          return N;
 9      end max_height_binary;
10  
11  begin
12      discrete node_pointer := root
13              new node_pointer := node_pointer.left | node_pointer.right
14          with h := max_height_binary (N) + 1
15                                            -- for null-case
16              new h = h - 1
17      loop
18          if node_pointer = NULL then
19              return NULL;
20          elsif key (node_pointer) = key_to_search then
21              return node_pointer;
22          elsif key (node_pointer) < key_to_search then
23              node_pointer := node_pointer.left;
24          else
25              node_pointer := node_pointer.right;
26          end if;
27      end loop;
28  end bintree_search;

[ Sourcefile ]

Notes on design

The original implementation in traditional high-level-languages like Pascal or C uses a repeat (or while) construct, which we replaced by a discrete loop with a remainder function.

The remainder function variable is initialized with the maximum height of the tree (line 14) and decremented by 1 (line 16) for every node traversed. We had to add 1 to the maximum height for the case of an empty binary tree (root = NULL).

Worst Case Performance

The defining property of a binary tree is that for each node all nodes with smaller keys are in the left subtree and all nodes in the right subtree have larger (or equal) keys.

The following binary tree is built by inserting 4 nodes in reverse order refering to their keys (i.e., 4 - 3 - 2 - 1).

In this instance, to find the node with key 1, every node has to be traversed and the traversal degrades to a linear traversal with N comparisons in the worst case!

Selected Bibliography

[Meh84, p. 152] [Ott93, p. 275] [Sed88, p. 37] [Wyk88, p. 164]

[ Samples Overview | Bibliography | WOOP Project ]