get TreeNode by number

Question

I am creating a heap from a binary tree in java. My implementation looks like this:

public class Heap <P extends Comparable<P>,D> {
  // ATTRIBUTES
  private TreeNode<P,D> root;
  private int size;

  // CONSTRUCTOR
  PriorityQueue() {
    this.root = null;
    this.last = null;
    this.size = 0;
  }

  class TreeNode<P,D> {
    // ATTRIBUTES
    P priority;
    D data;
    TreeNode<P,D> left;
    TreeNode<P,D> right;

    // CONSTRUCTOR
    TreeNode(P priority, D data, TreeNode<P,D> left, TreeNode<P,D> right) {
      this.priority = priority;
      this.data = data;
      this.left = left;
      this.right = right;
    }
    TreeNode(P priority, D data) {
      this(priority, data, null, null);
    }
}

Now I want to get the nth element of my node. I thought, that it would be smart to convert n to a binary string, pop the first 1 and then go left for each 0 and right for each 1.

That doesn't seem too hard, but now my problem is, how I should create an output like like root.left.left.right to get to the 9th element. I don't just wanna get a copy, that is easy (see the getNode(int n) function below), I want a reference to that node, so I can add a new node in that spot for example.

public TreeNode<P,D> getNode(int n) {
  String binString = Integer.toBinaryString(n);
  char[] binChars = binString.substring(1, binString.length()).toCharArray();
  TreeNode<P,D> node = this.root;
  for( char c : getNodePath(n) ){
    if( c == '0' ){
      node = node.left;
    } else if( c == '1' ){
      node = node.right;
    }
  }
  return node;
}

Is that even possible in java? In python I would just create a ".left.left.right" String and use run, but that doesn't seem to be possible in java.

Answer 1

The way you've structured your data, what you need is not a reference to the node n (which you are already getting), but a reference to its parent.

So for .left.left.right

you need to cut off the last bit and call getNode with .left.left

that will give you your Node's parent Node. The target node itself you can refer to by using the returned parent node and using the bit you cut off (.right)

parent.right

Also that way you can reassign the node by parent.right = new-node

btw, you don't need to create a binary string to implement your scheme. You just need to use the shift operators and 'bitwise AND'