Tree Node API and implementation

This article has the dual purpose of introducing Binary Tree exercises in this website and presenting the implementation of the binary tree node that they use.

• Number of Tree Nodes - counting the number of nodes in a tree is the most straightforward exercise, and therefore ideal for developers that are not familiar with recursion.
• Strict Binary Tree Check - this Java exercise is slightly trickier than just counting the number of nodes.
• Perfect Binary Tree Check and Complete Binary Tree Check - advanced recursion exercises.

Here is the implementation of TreeNode used on several exercises on this site.

public class TreeNode {
    private TreeNode left;
    private TreeNode right;

    public TreeNode() {
    }

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

    public TreeNode left() {
        return left;
    }

    public TreeNode right() {
        return right;
    }
}

Even though you will not need this for completing any exercise, here is the implementation of the toString() method. We display the actual and expected trees using this toString() method.

    @Override
    public String toString() {
        return toStringNode("N", this);
    }

    private String toStringNode(String parentName, TreeNode node) {
        String strNode = "";
        if (node != null) {
            strNode += parentName;
            if (node.left != null || node.right != null) {
                strNode += "(" + toStringNode(parentName + "1", node.left) + "," +
                        toStringNode(parentName + "2", node.right) + ")";
            }
        }
        return strNode;
    }

Binary tree exercises are frequently used in code interviews, mostly because they use recursion. Recursion usage is rare in imperative programming, and even the most passionate advocates of functional programming rarely use it in practice, so you may be wondering why interviewers like to ask code problems involving recursion. The reason is simple: recursion exercises are tricky, and interviewers use those to test the candidate smartness.