Binary Search Tree Depth-First Traversal

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

Depth-first traversal is divided into three types: preorder tree walk, inorder tree walk, and postorder tree walk, which are respectively:

  • 1. Preorder Traversal:Visit the current node first, then recursively visit the left and right subtrees in order.
  • 2. Inorder Traversal: First recursively visit the left subtree, then visit itself, then recursively visit the right subtree.
  • 3. Postorder Traversal: First recursively visit the left and right subtrees, then visit the current node itself.

Preorder Traversal Result Diagram:

Corresponding Code Example:

...
// Perform preorder traversal on the binary search tree rooted at node, 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, 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, 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 Package Download:Download

src/example/binary/Traverse.java file code:

package example.binary;

/**
* Priority traversal
 */

public class Traverse<Key extends Comparable<Key>, Value>  {

    // The nodes in the tree are a private class; the outside world does not need to know the specific implementation of the 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, constructs an empty binary search tree by default
    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) data pair into the binary search tree
    public void insert(Key key, Value value){
        root = insert(root, key, value);
    }

    // Check whether the key exists in the binary search tree
    public boolean contain(Key key){
        return contain(root, key);
    }

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

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

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

    // Postorder 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 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 whether the binary search tree rooted at node contains a node with key value key, using 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 );
    }

    // Find the value corresponding to key in the binary search tree rooted at node, recursive algorithm
    // Return NULL if the value does not exist
    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 preorder traversal on the binary search tree rooted at node, recursive algorithm
    private void preOrder(Node node){

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

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

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

    // Perform postorder traversal on 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);
        }
    }
}
other extensions