Create a tree from a list of nodes with parent pointers only

Question

I want you to pick my code apart and give me some feedback on how I could make it better or more simple.

class TreeNode {
    private TreeNode left;
    private TreeNode right;
    private TreeNode parent;
    int item;

    public TreeNode (TreeNode left, TreeNode right, TreeNode parent, int item) {
        this.left = left;
        this.right = right;
        this.parent = parent;
        this.item = item;
    }

    public int getItem() {
        return item;
    }

    public void setItem(int item) {
        this.item = item;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    public TreeNode getParent() {
        return parent;
    }

    public void setParent(TreeNode parent) {
        this.parent = parent;
    }
}

public class Ebay {

    private TreeNode root;

    public Map<TreeNode, List<TreeNode>> getMap (List<TreeNode> listOfTreeNodes) {
        final Map<TreeNode, List<TreeNode>> map = new HashMap<TreeNode, List<TreeNode>>();
        for (TreeNode treeNode : listOfTreeNodes) {
            if (map.get(treeNode.getParent()) != null) {
                map.get(treeNode.getParent()).add(treeNode);
            } else {
                List<TreeNode> list = new ArrayList<TreeNode>();
                list.add(treeNode);
                map.put(treeNode.getParent(), list);
            }
        }
        return map;
    }

    public void soStuff (List<TreeNode> listOfTreeNode)  {

        final Map<TreeNode, List<TreeNode>> map = getMap (listOfTreeNode);
        root = map.get(null).get(0);

        constructTree ( map , root);
    }


    public TreeNode constructTree (Map<TreeNode, List<TreeNode>> map, TreeNode node) {
        if (map.containsKey(node)) {
            List<TreeNode> list = map.get(node);
            node.setLeft(constructTree(map, map.get(node).get(0)));
            if (list.size() == 2) {
                node.setRight(constructTree(map, map.get(node).get(1)));
            }
        }
        return node;
    }

Answer 1

Your TreeNode class is mostly allright. But you have to be careful when handling trees with parent pointers, or the tree could go out of sync, and deteriorate to a weird class. A setParent on its own is silly. The setLeft and setRight should also make sure to set the parent of the new child node:

public void setLeft(TreeNode left) {
  this.left = left;
  left.parent = this;
}

Do not force a user of your class to do this bookkeeping.

Your item is weird. It is the only non-private field, and is an int. Use generics, so that your tree can carry any type.

A usable tree implementation will implement certain collection interfaces like Iterable.

---

Your Ebay class is very weird.

The methods getMap and constructTree are public, but are not very useful outside of that class. Both should also be static.

It is not immediately obvious what soStuff does. In seems to be a constructor, or initializer. Why not name it as such?

You use a HashMap, but do not provide a custom hashing method for TreeNode. While you inherit one from Object, this isn't terribly advisable.

What these three methods do is:

• You get a list of TreeNodes which only point to their parent. The task is to link these to a full tree.
• You build a map that maps parent nodes to a list of childs.
• You then assign the first item in each list to parent.left, the 2nd to parent.right, if applicable.

Your solution has the advantage that it builds the tree top-down, recursively, and won't touch any nodes that will not be in the final tree. It comes at the cost of building an entirely unneccessary HashMap. The following implementation assumes that no unrelated nodes are in the input list:

/**
 * Expects a TreeNode collection where each node points to its parent.
 * Builds the full tree and returns the root (which has to have a
 * null parent).
 */
public static TreeNode linkToTree(Iterable<TreeNode> nodes) {
  /* Building the tree.
   *
   * At some point, we *will* find the root, thus getting a
   * handle on the tree. If not, "null" will be returned, which
   * is a good error case.
   * 
   * Each node already knows its parent, so we just add the node
   * as a new child to the parent. We treat a "null" slot as empty.
   * First, we fill the left slot, then overwrite the right slot
   * without any checks – last one wins out.
   */

  TreeNode root;

  for (TreeNode node : nodes) {
    final TreeNode parent = node.getParent();

    // try to detect the root node
    if (parent == null) {
      root = node;
    }
    // add this node to the parent's left slot if it's empty
    else if (parent.getLeft() == null) {
      parent.setLeft(node);
    }
    // … else overwrite right slot
    else {
      parent.setRight(node);
    }
  }

  return root;
}

What did I do differently?

• This method is public static. It is reusable, and does not modify any instance members.
• It takes any Iterable, not just a List. Why be unneccessarily specific?
• It is documented. Note that I have a large comment inside my method explaining why I wrote my code this way, and point out a certain edge case (not finding any root). Inside my if/else, I have smaller comments pointing out what each test means.
• I did not use recursion. While recursion can be very elegant, it is to be avoided on the JVM.
• It uses less memory than your solution, is shorter, and more elegant. Due to all of the comments, the implementation shouldn't be harder to understand than your code, even though the underlying algorithm is slightly more difficult.
• I don't use nondescriptive variable names like map.

Answer 2

Technically this is a binary tree node and not a tree node. In order to make it a tree node, it would have a list of child nodes instead of one left child and one right child. The class could add a list of children or rename TreeNode to BinaryTreeNode for higher cohesion.