Uniquely number nodes of a Binary Tree

Question

How would I go about setting an index for each node after generating a binary tree?

      (a)               (1)
   (x)   (r)   =>     (2)  (3)
  (o)(t)(t)(x)      (4)(5)(6)(7)

So I can then use a call such as getIndex()at a particular node to return its index.

My tree class:

public class BT<E>{
   E value;
   BT<E> left, right;
   int Index;

   public BT(E value)
   {
      this.value=value;
   }   

   public BT (E value, BT left, BT right) 
   {
      this.value = value;
      this.left = left;
      this.right = right;
   }

Are you ok with traversing the tree once more after you have fully created it, or are you trying to initialize this index during the first pass when you create the tree? — NoseKnowsAll, Aug 14 '15 at 16:45
@NoseKnowsAll I need it to be done after the tree is fully created. — RK2015, Aug 14 '15 at 16:48

score 1 · Accepted Answer · edited May 23 '17 at 11:52

Breadth-first traversal.

Queue<BT> queue = new LinkedList<BT>() ;

public void breadth(BT root) {
    if (root == null)
        return;

    queue.clear();
    queue.add(root);
    int index = 0;
    while(!queue.isEmpty()){
        BT node = queue.remove();
        node.Index = index;
        index++;
        if(node.left != null) queue.add(node.left);
        if(node.right != null) queue.add(node.right);
    }

}

Adapted from here.

Kevin · Answer 2 · 2015-08-14T18:28:07.173

So you are to implement a procedure getIndex(int index) which has to return you the node with that index?

If so, you are looking for an efficient way to represent a binary tree. You could traverse the tree for each call to getIndex but this wouldn't be efficient...

An efficient solution is to store the complete binary tree in an array, because of the O(1) access it provides. Store a node n at index n in the array and its child nodes at index 2*n and (2*n) - 1. But here the restrictions are that the tree has to be complete and the size of an array is not variable (if the binary tree becomes too big, a bigger array (usually twice as big) should be made and all elements should be copied).

This is a handy solution because :

Node access is in O(1) but a procedure like addNode() would become amortized in O(1). (*)
A node does not have to remember it's child nodes --> this.left becomes this.left() with the implementation of left() provided below.

A possible implementation for left() procedure.

static int[] binaryTreeArray = new int[maxTreeSize]; // BT of integers for example
...
public int left() { // returns integer or ... (type of your nodes)
    return binaryTreeArray[(this.Index)*2]; // O(1)
}

(*) An addNode()-like procedure would add nodes in O(1) (binaryTreeArray[index] = nodeValue;) most of the time but when the binaryTreeArray is full it will have to make a bigger array that is usually twice as big (O(n) for the copying). It can be shown that this has an amortized cost of O(1) but this has no added value for this answer.

score 0 · Answer 3 · answered Aug 14 '15 at 17:08

If you are doing this after the tree is fully created, then something that uses level-order traversal will work. It's not terribly efficient, but it's straight-forward recursion:

/* Method to set index based on level-order traversal of tree */
public void initIndices(BT root) {
    int maxIndexSoFar = 0;
    for (int d = 1; d <= root.height(); ++d)
        maxIndexSoFar = setIndexAtLevel(root, d, maxIndexSoFar);
}

/* Method to set index of all nodes at a given level */
private int setIndexAtLevel(BT node, int level, int index) {
    if (tree == null)
        return index;
    if (level == 1) {
        index++;
        node.setIndex(index);
        return index;
    }
    else if (level > 1) {
        int newIndex = setIndexAtLevel(node.left, level-1, index);
        newIndex = setIndexAtLevel(node.right, level-1, newIndex);
        return newIndex;
    }
    return -1;
}

I'll leave you to create the height() method and setIndex() methods. Fair warning, I have not tested this at all, so pardon any typos.

Uniquely number nodes of a Binary Tree

3 Answers3