_024_BinarySearchTree.java Documentation#

Java Implementation of a Binary Search Tree#

This Java code implements a Binary Search Tree (BST) data structure, including methods for construction, traversal, and node deletion. The code also includes a detailed explanation within the code itself, describing the properties and uses of BSTs.

1. Overview#

The code defines a Node class representing nodes in the BST, and a _024_BinarySearchTree class containing methods to:

  • Construct a BST: From a string array representing the tree structure level-order.
  • Traverse the BST: Using pre-order, post-order, and in-order traversal methods.
  • Delete nodes: Handles leaf nodes, nodes with one child, and nodes with two children.
  • Calculate the height of the tree: Returns the height of the BST.

2. Detailed Explanation of Key Methods and Classes#

2.1 Node Class# 

static class Node {
    int val;
    Node right;
    Node left;
    public Node(int val){
        this.val = val;
    }
}

This inner class represents a single node in the BST. It stores an integer value (val) and references to its left and right child nodes (left and right).

2.2 height(Node root) Method# 

public static int height(Node root){
    if (root == null || (root.left == null && root.right == null)) return 0;
    return 1+Math.max(height(root.left),height(root.right));
}

This method recursively calculates the height of the BST. The height is the number of edges on the longest path from the root to a leaf node. An empty tree or a tree with only the root node has a height of 0.

2.3 constructTree(String[] arr) Method# 

public static Node constructTree(String[] arr){
    int x = Integer.parseInt(arr[0]);
    int n = arr.length;
    Node root = new Node(x);
    Queue<Node> q = new LinkedList<>();
    q.add(root);
    int i = 1;
    while(i < n-1){
        Node temp = q.remove();
        Node left = new Node(10);
        Node right = new Node(100);
        if (arr[i].isEmpty() || arr[i].equals("null")) left = null;
        else{
            left.val= Integer.parseInt(arr[i]);
            q.add(left);
        }
        if (arr[i + 1].isEmpty() || arr[i].equals("null")) right = null;
        else{
            right.val = Integer.parseInt(arr[i+1]);
            q.add(right);
        }
        temp.left = left;
        temp.right = right;
        i+=2;
    }
    return root;
}

This method constructs a BST from a level-order string array representation. It uses a queue (LinkedList) for breadth-first traversal. The array should contain the node values level by level, from left to right. Empty strings or “null” represent missing child nodes. This implementation has a flaw: It creates nodes with default values (10 and 100) even if the input suggests a null child. It should be improved to correctly handle null children without creating unnecessary nodes.

2.4 Traversal Methods (preOrder, postOrder, inOrder)#

These methods implement the three standard tree traversals:

  • Pre-order: Root, Left, Right
  • Post-order: Left, Right, Root
  • In-order: Left, Root, Right (In-order traversal of a BST yields a sorted sequence of node values).

The implementation is recursive.

2.5 Deletion Methods (deleteLeafNode, deleteNodeHavingOneNode, deleteNodeHavingTwoNode)#

These methods handle the deletion of nodes with different numbers of children:

  • deleteLeafNode: Deletes a leaf node (a node with no children).
  • deleteNodeHavingOneNode: Deletes a node with one child.
  • deleteNodeHavingTwoNode: Deletes a node with two children. This is the most complex case, as it requires finding the inorder predecessor (or successor) to maintain the BST property. The code’s implementation of this is not fully correct, it contains errors and is inefficient.

3. Code Workflow and Logic Flow#

The main method demonstrates the usage of the class. It constructs two BSTs using constructTree, then performs traversals using the preOrder, postOrder, and inOrder methods. Finally, it attempts to delete a node using deleteNodeHavingOneNode. The logic of the deletion methods is recursive and searches for the node to delete, based on whether the value is greater or less than the current node’s value.

4. Use Cases and Examples#

Binary Search Trees are used in various applications where efficient searching, insertion, and deletion are required:

  • Databases: Indexing data for faster lookups.
  • Symbol tables: Storing and retrieving data based on keys.
  • Implementation of other data structures: Sets, maps, and priority queues.

5. Important Notes and Considerations#

  • Error Handling: The code lacks robust error handling (e.g., handling invalid input to constructTree).
  • Balancing: The code doesn’t implement any self-balancing algorithms (like AVL trees or red-black trees). An unbalanced BST can degrade to O(n) search time in the worst case (skewed tree).
  • DeleteNodeHavingTwoNode Efficiency and Correctness: This method is highly inefficient and contains logical errors; especially the way it reconnects the tree after replacing the node with its inorder predecessor. A more robust and efficient algorithm should be implemented.
  • constructTree Improvement: As mentioned before, the constructTree method should be improved to correctly handle null values in the input array without creating unnecessary nodes with default values.

The current implementation provides a basic understanding of BST operations but needs significant improvements for production use. Adding self-balancing and more robust error handling would significantly enhance its practicality.

🔗 View Original Code on GitHub

This documentation was automatically generated from the source code.