Programming Interviews Exposed: Secrets to Landing Your Next Job, 3rd Edition

Trees

A tree is made up of nodes (data elements) with zero, one, or several references (or pointers) to other nodes. Each node has only one other node referencing it. The result is a data structure that looks like Figure 5-1.

Figure 5-1

As in a linked list, a node is represented by a structure or class, and trees can be implemented in any language that includes pointers or references. In object-oriented languages you usually define a class for the common parts of a node and one or more subclasses for the data held by a node. For example, the following are the C# classes you might use for a tree of integers:

public class Node {
    public Node[] children;
}

public class IntNode : Node {
    public int value;
}

In this definition, children is an array that keeps track of all the nodes that this node references. For simplicity, these classes expose the children as public data members, but this isn’t good coding practice. A proper class definition would make them private and instead expose public methods to manipulate them. A somewhat more complete Java equivalent (with methods and constructors) to the preceding classes is:

public abstract class Node { private Node[] children; public Node( Node[] children ){ this.children = children; } public int getNumChildren(){ return children.length; } public Node getChild( int index ){ return children[ index ]; } } public class IntNode extends Node ...