Stanford introduction

    This [the following section until marked as end of Stanford University items] is article #110 in the Stanford CS Education Library. This and other free CS materials are available at the library (http://cslibrary.stanford.edu/). That people seeking education should have the opportunity to find it. This article may be used, reproduced, excerpted, or sold so long as this paragraph is clearly reproduced. Copyright 2000-2001, Nick Parlante, nick.parlante@cs.stanford.edu. [Stanford items are marked by a very light Stanford cardinal background.]

Related CSLibrary Articles

• Linked List Problems (http://cslibrary.stanford.edu/105/) -- a large collection of linked list problems using various pointer techniques (while this binary tree article concentrates on recursion)
• Pointer and Memory (http://cslibrary.stanford.edu/102/) -- basic concepts of pointers and memory
• The Great Tree-List Problem (http://cslibrary.stanford.edu/109/) -- a great pointer recursion problem that uses both trees and lists

Section 1 -- Introduction To Binary Trees

    A binary tree is made of nodes, where each node contains a “left” pointer, a “right” pointer, and a data element. The “root” pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller “subtrees” on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.

    A “binary search tree” (BST) or “ordered binary tree” is a type of binary tree where the nodes are arranged in order: for each node, all elements in its left subtree are less-or-equal to the node (<=), and all the elements in its right subtree are greater than the node (>). The tree shown above is a binary search tree -- the “root” node is a 5, and its left subtree nodes (1, 3, 4) are <= 5, and its right subtree nodes (6, 9) are > 5. Recursively, each of the subtrees must also obey the binary search tree constraint: in the (1, 3, 4) subtree, the 3 is the root, the 1 <= 3 and 4 > 3. Watch out for the exact wording in the problems -- a “binary search tree” is different from a “binary tree”.

    The nodes at the bottom edge of the tree have empty subtrees and are called “leaf” nodes (1, 4, 6) while the others are “internal” nodes (3, 5, 9).

Binary Search Tree Niche

    Basically, binary search trees are fast at insert and lookup. The next section presents the code for these two algorithms. On average, a binary search tree algorithm can locate a node in an N node tree in order lg(N) time (log base 2). Therefore, binary search trees are good for “dictionary” problems where the code inserts and looks up information indexed by some key. The lg(N) behavior is the average case -- it’s possible for a particular tree to be much slower depending on its shape.

Strategy

    Some of the problems in this article use plain binary trees, and some use binary search trees. In any case, the problems concentrate on the combination of pointers and recursion. (See the articles linked above for pointer articles that do not emphasize recursion.)

    For each problem, there are two things to understand…

• The node/pointer structure that makes up the tree and the code that manipulates it
• The algorithm, typically recursive, that iterates over the tree

    When thinking about a binary tree problem, it’s often a good idea to draw a few little trees to think about the various cases.

Typical Binary Tree Code in C/C++

    As an introduction, we’ll look at the code for the two most basic binary search tree operations -- lookup() and insert(). The code here works for C or C++. … In Java, the key points in the recursion are exactly the same as in C or C++. In fact, I created the Java solutions by just copying the C solutions, and then making the syntactic changes. The recursion is the same, however the outer structure is slightly different.

    In C or C++, the binary tree is built with a node type like this…

struct node {
    int data;
    struct node* left;
    struct node* right;

}

    {NOTE; the original Stanford document separated the C/C++ and the Java discusssions. The material is interwoven here because this book uses the approach of teaching abasic concept and then showing it in multiple languages.]

Pointer Changing Code

    There is a common problem with pointer intensive code: what if a function needs to change one of the pointer parameters passed to it? For example, the insert() function below [moved to tree insert] may want to change the root pointer. In C and C++, one solution uses pointers-to-pointers (aka “reference parameters”). That’s a fine technique, but here we will use the simpler technique that a function that wishes to change a pointer passed to it will return the new value of the pointer to the caller. The caller is responsible for using the new value. Suppose we have a change() function that may change the the root, then a call to change() will look like this…

// suppose the variable "root" points to the tree
root = change(root);

    We take the value returned by change(), and use it as the new value for root. This construct is a little awkward, but it avoids using reference parameters which confuse some C and C++ programmers, and Java does not have reference parameters at all. This allows us to focus on the recursion instead of the pointer mechanics. (For lots of problems that use reference parameters, see CSLibrary #105, Linked List Problems, http://cslibrary.stanford.edu/105/).

Binary Tree Problems

    Here are 14 binary tree problems in increasing order of difficulty. Some of the problems operate on binary search trees (aka “ordered binary trees”) while others work on plain binary trees with no special ordering. The next section, Section 3, shows the solution code in C/C++. Section 4 gives the background and solution code in Java. The basic structure and recursion of the solution code is the same in both languages -- the differences are superficial.

    Reading about a data structure is a fine introduction, but at some point the only way to learn is to actually try to solve some problems starting with a blank sheet of paper. To get the most out of these problems, you should at least attempt to solve them before looking at the solution. Even if your solution is not quite right, you will be building up the right skills. With any pointer-based code, it’s a good idea to make memory drawings of a a few simple cases to see how the algorithm should work.

    [These problems are repeated in separate subchapters to allow additional commentary. In the original file the problems and the solutions were separated into differetn sections. Here they are grouped together. It is strongly recommended that readers follow Dr. Nick Parlante’s advice and attempt to solve the problems before reading the answers.]

• tree lookup
• tree insert

copyright notice

    This [the quoted passages above] is article #110 in the Stanford CS Education Library. This and other free CS materials are available at the library (http://cslibrary.stanford.edu/). That people seeking education should have the opportunity to find it. This article may be used, reproduced, excerpted, or sold so long as this paragraph is clearly reproduced. Copyright 2000-2001, Nick Parlante, nick.parlante@cs.stanford.edu. [Stanford items are marked by a very light Stanford cardinal background.]

end of Stanford introduction