Register

# 17.3. Binary Trees Part 1¶

## 17.3.1. Binary Trees Part 1¶

### 17.3.1.1. Binary Trees¶

A binary tree is made up of a finite set of nodes that is either empty or consists of a node called the root together with two binary trees, called the left and right subtrees, which are disjoint from each other and from the root.

Notation: Node, children, edge, parent, ancestor, descendant, path, depth, height, level, leaf node, internal node, subtree.

### 17.3.1.3. Binary Tree Node Class¶

interface BinNode { // Binary tree node ADT
// Get and set the element value
public Object value();
public void setValue(Object v);

// return the children
public BinNode left();
public BinNode right();

// return TRUE if a leaf node, FALSE otherwise
public boolean isLeaf();
}

interface BinNode<E> { // Binary tree node ADT
// Get and set the element value
public E value();
public void setValue(E v);

// return the children
public BinNode<E> left();
public BinNode<E> right();

// return TRUE if a leaf node, FALSE otherwise
public boolean isLeaf();
}


### 17.3.1.4. Question¶

• Write a recursive function named count that, given the root to a binary tree, returns a count of the number of nodes in the tree. Function count should have the following prototype:

int count(BinNode root)


### 17.3.1.5. Traversals¶

• Any process for visiting the nodes in some order is called a traversal.

• Any traversal that lists every node in the tree exactly once is called an enumeration of the tree’s nodes.

• Preorder traversal: Visit each node before visiting its children.

• Postorder traversal: Visit each node after visiting its children.

• Inorder traversal: Visit the left subtree, then the node, then the right subtree.

### 17.3.1.6. Preorder Traversal (1)¶

static void preorder(BinNode rt) {
if (rt == null) return; // Empty subtree - do nothing
visit(rt);              // Process root node
preorder(rt.left());    // Process all nodes in left
preorder(rt.right());   // Process all nodes in right
}

static <E> void preorder(BinNode<E> rt) {
if (rt == null) { return; } // Empty subtree - do nothing
visit(rt);              // Process root node
preorder(rt.left());    // Process all nodes in left
preorder(rt.right());   // Process all nodes in right
}


Settings

Saving...
Server Error
Resubmit

### 17.3.1.8. How not to write a traversal¶

// This is a bad idea
static void preorder2(BinNode rt) {
visit(rt);
if (rt.left() != null) preorder2(rt.left());
if (rt.right() != null) preorder2(rt.right());
}

// This is a bad idea
static <E> void preorder2(BinNode<E> rt) {
visit(rt);
if (rt.left() != null) { preorder2(rt.left()); }
if (rt.right() != null) { preorder2(rt.right()); }
}

Problems:
This has a major bug
It puts the focus in the wrong place: Should focus on the current node, not the children. This version is therefore more complicated.

### 17.3.1.9. Recursion Examples¶

static int count(BinNode rt) {
if (rt == null) return 0;  // Nothing to count
return 1 + count(rt.left()) + count(rt.right());
}

static <E> int count(BinNode<E> rt) {
if (rt == null) { return 0; }  // Nothing to count
return 1 + count(rt.left()) + count(rt.right());
}

Settings

Saving...
Server Error
Resubmit