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

5.1. Trees

A tree is made up of nodes (data elements) with zero, one, or several references to other nodes. Each node has only one other node referencing it. The result is a data structure that looks like 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, these 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;
}

Figure 5.1. Figure 5-1

In this definition, children is an array that keeps track of all the nodes that this node references. Note that for simplicity we exposed the children as public data members. A proper class definition would make them private and expose methods to manipulate them. A fuller Java equivalent (with methods and constructors) to the preceding classes would be as follows:

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 { private int value; public IntNode( Node[] children, int ...