Binary Search Tree Depth-First Traversal

Binary search tree traversal is divided into two main categories: depth-first traversal and level-order traversal.

Depth-first traversal includes three types: preorder traversal (preorder tree walk), inorder traversal (inorder tree walk), and postorder traversal (postorder tree walk), respectively:

• 1. Preorder Traversal: Visit the current node first, then recursively visit the left and right subtrees.

• 2. Inorder Traversal: Recursively visit the left subtree, then visit the current node, and finally recursively visit the right subtree.

• 3. Postorder Traversal: Recursively visit the left and right subtrees, then visit the current node.

Preorder Traversal Result Diagram:

Corresponding Code Example:

...
// Perform preorder traversal on the binary search tree rooted at node, using a recursive algorithm
private void preOrder(Node node){

    if( node != null ){
        System.out.println(node.key);
        preOrder(node.left);
        preOrder(node.right);
    }
}
...

Inorder Traversal Result Diagram:

Corresponding Code Example:

...
// Perform inorder traversal on the binary search tree rooted at node, using a recursive algorithm
private void inOrder(Node node){

    if( node != null ){
        inOrder(node.left);
        System.out.println(node.key);
        inOrder(node.right);
    }
}
...

Postorder Traversal Result Diagram:

Corresponding Code Example:

...
// Perform postorder traversal on the binary search tree rooted at node, using a recursive algorithm
private void postOrder(Node node){

    if( node != null ){
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.key);
    }
}
...

Java Example Code

Source Code Download: Download

src/tutorialpro/binary/Traverse.java File Code:

package tutorialpro.binary;

/**
 * Priority Traversal
 */

public class Traverse&lt;Key extends Comparable<Key>, Value>  {

    // Nodes in the tree are a private class, external parties do not need to know the specific implementation of binary search tree nodes
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }

    private Node root;  // Root node
    private int count;  // Number of nodes in the tree

    // Constructor, default to an empty binary search tree
    public Traverse() {
        root = null;
        count = 0;
    }

    // Return the number of nodes in the binary search tree
    public int size() {
        return count;
    }

    // Return whether the binary search tree is empty
    public boolean isEmpty() {
        return count == 0;
    }

    // Insert a new (key, value) pair into the binary search tree
    public void insert(Key key, Value value){
        root = insert(root, key, value);
    }

    // Check if the binary search tree contains the key
    public boolean contain(Key key){
        return contain(root, key);
    }

// Search for the value corresponding to the key in the binary search tree. If the value does not exist, return null.
public Value search(Key key){
    return search(root, key);
}

// Pre-order traversal of the binary search tree
public void preOrder(){
    preOrder(root);
}

// In-order traversal of the binary search tree
public void inOrder(){
    inOrder(root);
}

// Post-order traversal of the binary search tree
public void postOrder(){
    postOrder(root);
}

//********************
//* Helper functions for the binary search tree
//********************

// Insert node (key, value) into the binary search tree rooted at node using a recursive algorithm
// Return the root of the binary search tree after inserting the new node
private Node insert(Node node, Key key, Value value){

    if(node == null){
        count++;
        return new Node(key, value);
    }

    if(key.compareTo(node.key) == 0)
        node.value = value;
    else if(key.compareTo(node.key) < 0)
        node.left = insert(node.left, key, value);
    else // key > node.key
        node.right = insert(node.right, key, value);

    return node;
}

// Check if the binary search tree rooted at node contains a node with the key, using a recursive algorithm
private boolean contain(Node node, Key key){

    if(node == null)
        return false;

    if(key.compareTo(node.key) == 0)
        return true;
    else if(key.compareTo(node.key) < 0)
        return contain(node.left, key);
    else // key > node.key
        return contain(node.right, key);
}

// Search for the value corresponding to the key in the binary search tree rooted at node using a recursive algorithm
// If the value does not exist, return null
private Value search(Node node, Key key){

    if(node == null)
        return null;

    if(key.compareTo(node.key) == 0)
        return node.value;
    else if(key.compareTo(node.key) < 0)
        return search(node.left, key);
    else // key > node.key
        return search(node.right, key);
}

// Perform a pre-order traversal of the binary search tree rooted at node using a recursive algorithm
private void preOrder(Node node){

    if(node != null){
        System.out.println(node.key);
        preOrder(node.left);
        preOrder(node.right);
    }
}

// Perform an in-order traversal of the binary search tree rooted at node using a recursive algorithm
private void inOrder(Node node){

    if(node != null){
        inOrder(node.left);
        System.out.println(node.key);
        inOrder(node.right);
    }
}

// Perform a post-order traversal of the binary search tree rooted at node using a recursive algorithm
private void postOrder(Node node){

    if(node != null){
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.key);
    }
}

if( node != null ){
    inOrder(node.left);
    System.out.println(node.key);
    inOrder(node.right);
}
}

// Post-order traversal of the binary search tree rooted at node, recursive algorithm
private void postOrder(Node node){

    if( node != null ){
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.key);
    }
}
}