Introduction to Binary Trees - Advanced Topics in Java: Core Concepts in Data Structures - page 235

8.8 Building a Binary Tree with Parent Pointers
We have seen how to perform pre-order, in-order, and post-order traversals using recursion (which is implemented
using a stack) or an explicit stack. We now look at a third possibility. First, let's build the tree so that it contains
“parent” pointers.
Each node now contains an additional field—a pointer to its parent. The parent field of the root will be null . For
example, in the tree shown in Figure 8-8 , H 's parent field points to F , A 's parent field points to G , and G 's parent field points to C .

C

G

E

N

F B A

K

J

H

Figure 8-8. A binary tree with some parent pointers

To represent such a tree, we now declare TreeNode as follows:

class TreeNode {
NodeData data;
TreeNode left, right, parent;

public TreeNode(NodeData d) {
data = d;
left = right = parent = null;
}
} //end class TreeNode

We can now rewrite buildTree as follows:

public static TreeNode buildTree(Scanner in) {
String str = in.next();
if (str.equals("@")) return null;
TreeNode p = new TreeNode(new NodeData(str));
p.left = buildTree(in);
if (p.left != null) p.left.parent = p;
p.right = buildTree(in);
if (p.right != null) p.right.parent = p;
return p;
} //end buildTree

After we build the left subtree of a node p , we check whether it is null . If it is, there is nothing further to do. If it is
not and q is its root, we set q.parent to p . Similar remarks apply to the right subtree.