Title: Map between nodes and node numbers in a binary tree in C#

For more information about trees and other algorithmic topics, see my book Essential Algorithms: A Practical Approach to Computer Algorithms.

Suppose you have a binary tree with the nodes numbered as shown on the right. Note that it may have some missing nodes. For example, the binary tree shown here has nodes 10 and 13 but no other nodes on that level.

This example shows how you can map between node objects and numbers in the binary tree. In other words, if you have a reference to a particular node, you should be able to climb over the tree to find its number. Conversely if you know a node's number, you should be able to quickly climb through the tree to find the corresponding node.

If you move the mouse over a node, the program displays the node's label and its node number (which are the same in the sample binary tree) in the status message at the bottom of the form.

If you open the Data menu and select Find Node, a dialog appears. If you enter a node number and click OK, the program highlights the corresponding node.

Before I start explaining how to do this, you need to know how the tree is organized. Basically the TreeNode class represents a node in the binary tree. Each node has three key properties that refer to other TreeNode objects. Those properties are LeftChild, RightChild, and Parent. You can traverse the tree by using those properties.

Finding a Node's Number

Given a node, how do you find its number? This is actually pretty straightforward if you notice one key fact about the node numbering: If a node has number N, then its children have numbers 2 × N + 1 and 2 × N + 2.

The following NodeNumber method uses that fact to find a node's number.

// Return this node's number. public int NodeNumber() { // If we're the root node, return 0. if (Parent == null) return 0; // We are not the root node. // See if we are the left or right child. if (this == Parent.LeftChild) return Parent.NodeNumber() * 2 + 1; else return Parent.NodeNumber() * 2 + 2; }

If this node has no parent, then it is the binary tree's root node so the method returns 1.

If this node has a parent, the code figures out whether this node is the parent's left or right child. It then calls the parent's NodeNumber method to get the parent's node number and then uses that to figure out this node's number.

Finding a Number's Node

Given a node number, how do you find the corresponding node? This is more confusing than the other case. The key here is to notice that the bits in the number tell you which branches to take while traversing the binary tree.

First look at the number and, if it is 0, return the root node.

Next add one to the number and then consider the result's binary representation. Start at the root node and start at the second-to-leftmost bit. At each step, if the next bit you are considering is 0, move down the left branch. If the next bit is 1, move down the right branch.

For example, suppose you want to find node 10. Adding 1 to the number gives 11, which is 1011 in binary. Start at the root node and with the second bit from the left, which is a 0. That 0 tells us to move down the left branch to node number 1.

Now consider the next bit, which is the third from the left in 1011. That bit is a 1 so we move down the right branch to node 4.

The next bit, is the fourth from the left in 1011, is another 1 so we move down the right branch again to node 10.

At this point we have run out of bits so we have found the target node.

As you traverse the tree, if you ever follow a branch that doesn't lead to a node, then the target node isn't in the tree.

For another example, suppose you want to find node 13. Adding 1 to the number gives 14, which is 1110 in binary. Start at the root node. The second bit from the left is a 1 so we move down the right branch to node 2.

The third bit from the left is another 1 so we move down the right branch again to node 6.

The fourth bit is from the left is a 0 so we move down the left branch to node 13.

We're out of bits so we have found the desired node.

For a last example, suppose you want to find node 4. Adding 1 to the number gives 5, which is 101 in binary. Start at the root node. The second bit from the left is a 0 so we move down the left branch to node 1.

The third bit from the left is a 1 so we move down the right branch to node 4.

Again we're out of bits so we have found the desired node.

The following code shows how the program implements this algorithm.

// Find the indicated node in this subtree. public TreeNode<T> FindNodeByNumber(int number) { // If this is the root node, return it. if (number <= 0) return this; // Add 1 to the number so the numbers at each level // in the tree has the same number of bits. number++; // Find the least significant bit. int msb = FindMsb(number); // Climb down through the tree. TreeNode<T> node = this; for (int i = msb - 1; i >= 0; i--) { // Use this bit to decide which way to go. if ((number & (1 << i)) == 0) node = node.LeftChild; else node = node.RightChild; // See if we fell off the tree. if (node == null) return null; } // Return the current node. return node; } // Return the number's least significant bit. private int FindMsb(int number) { for (int i = 31; i >= 0; i--) if ((number & (1 << i)) != 0) return i; return -1; }

The FindNodeByNumber method searches the tree as described above. The FindMsb helper method searches a number from left-to-right to find its most significant digit and returns that digit's position in the number.

This program does a lot of other things besides traverse the tree. In particular, it lets you add and remove nodes and it displays the resulting tree. The program is based on the example Handle generic TreeNode mouse events in C# except it has been modified to work with binary trees instead of trees with arbitrary degree. See that example for information about how those other features work.

Download the example to experiment with it and to see additional details.