CODEWITHSUNDEEP
javaalgorithmbinary-tree
Mirrana
Mirrana

Reputation: 1731

How do I get the root of a binary tree without having parent links in a tree node?

I have as an assignment to do the following:

Write, document (internally) and test a Java program to solve the following problem:

Implement the binary tree ADT using a linked representation in which each node contains the following:

  • data
  • reference/link to the left child
  • reference/link to the right child

Assume that the data are integer values.

Implement the following operations (as described in Section 7.3 of the textbook):

  • size
  • isEmpty
  • eplace
  • root
  • left
  • right
  • hasLeft
  • hasRight
  • isInternal
  • isExternal
  • isRoot
  • insertLeft
  • insertRight
  • attach
  • remove

and also the following traversals:

  • preorder
  • postorder
  • inorder

I know how a binary tree works, and for the most part I have no problem doing this - but the problem I have is that I'm not allowed to have any variables in the node class other than the three given - that is, I cannot make a parent link. How can I check if a given node is the root of the tree if I can't have a link to a parent node?

Upvotes: 1

Views: 8746

Answers (3)

alzaimar
alzaimar

Reputation: 4622

Suppose you have an isolated node knowing only it's left and right linked nodes, and nothing else, there is no way in determining the root, unless you have a collection of nodes to test.

The obvious way -of course- is to use the root property of the surrounding Tree-structure which in fact defines the tree, i.e. all the other solutions presented here.

But, if, for some reason, you are not allowed to do this, you could do something as the following code which tests all nodes available. As a side effect, it also gives you an implementation of the 'parent' property.

In fact, the 'root' could be defined as 'the node with no parent'.

public TreeNode Parent(TreeNode node)
{
  TreeNode result = null;
  foreach (TreeNode candidate in allTheNodes)
    if (candidate.left == node || candidate.right == node)
      return candidate;

  return null;
}

public TreeNode root()
{
  foreach (node in allTheNodes)
    if (Parent(node)==null) 
      return node;

  return null;
}

Upvotes: 2

Stephen
Stephen

Reputation: 2424

With a BinaryTree you have nodes that have three attributes: 

int value; 
Node left;
Node right;

So if I wanted to build a tree I could do:

root = Node();
root.value = 5;
root.left = Node();
root.left.value = 3;
root.left.right = Node()
root.left.right.value = 4;
root.right = Node();
root.right.value = 6;
root.left.left = node();
root.left.left.value = 1;

Which would give a tree:

    5
   / \
  3   6
 / \
1   4

Now our root is holding all of this information and we can access any node attached to it through it.

So you need to write a wrapper for all of those operations, essentially. To check to see if an arbitrary node is the root, just compare it to the one you stored as root.

The structure is as follows:

public class BinaryTree{
    class Node {
        int value;
        Node left;
        Node right;
    }
    Node root;
    //method declarations
}

Upvotes: 1

Arsen Alexanyan
Arsen Alexanyan

Reputation: 3141

You can define BinaryTree class and keep Node root field in it. So You already know the root

Upvotes: 2

Related Questions