Binary Search Trees

BSTIterator.java

class BSTIterator {

    Stack<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        this.stack = new Stack<TreeNode>();
        this._leftmostInorder(root);
    }

    private void _leftmostInorder(TreeNode root) {
        while (root != null) {
            this.stack.push(root);
            root = root.left;
        }
    }

    public int next() {
        TreeNode topmostNode = this.stack.pop();

        if (topmostNode.right != null) {
            this._leftmostInorder(topmostNode.right);
        }

        return topmostNode.val;
    }

    public boolean hasNext() {
        return this.stack.size() > 0;
    }
}

IdenticalTrees.java

// Java program to check if two BSTs
// contain same set of elements
import java.util.*;
 
class Solution {

    static class Node {
        int data;
        Node left;
        Node right;
    };
 
    static Node newNode(int val)
    {
        Node temp = new Node();
        temp.data = val;
        temp.left = temp.right = null;
        return temp;
    }
 
    static void storeInorder(Node root, Vector<Integer> v)
    {
        if (root == null)
            return;
        storeInorder(root.left, v);
        v.add(root.data);
        storeInorder(root.right, v);
    }
 
    static boolean checkBSTs(Node root1, Node root2)
    {
        if (root1 == null && root2 == null)
            return true;
        if ((root1 == null && root2 != null)
            || (root1 != null && root2 == null))
            return false;
 
        Vector<Integer> v1 = new Vector<Integer>();
        Vector<Integer> v2 = new Vector<Integer>();
        storeInorder(root1, v1);
        storeInorder(root2, v2);

        return (v1.hashCode() == v2.hashCode());
    }

    public static void main(String[] args)
    {
        if (checkBSTs(root1, root2))
            System.out.print("YES");
        else
            System.out.print("NO");
    }
}

KthSmallestElement.java

// A simple inorder traversal based Java program
// to find k-th smallest element in a BST.
import java.io.*;
import java.util.*;

class Node {
	int data;
	Node left, right;
	int lCount;
	Node(int x)
	{
		data = x;
		left = right = null;
		lCount = 0;
	}
}

class Gfg {
	public static Node insert(Node root, int x)
	{
		if (root == null)
			return new Node(x);

		if (x < root.data) {
			root.left = insert(root.left, x);
			root.lCount++;
		}

		else if (x > root.data)
			root.right = insert(root.right, x);
		return root;
	}

	public static Node kthSmallest(Node root, int k)
	{
		if (root == null)
			return null;

		int count = root.lCount + 1;
		if (count == k)
			return root;

		if (count > k)
			return kthSmallest(root.left, k);

		return kthSmallest(root.right, k - count);
	}

	// main function
	public static void main(String args[])
	{
		Node root = null;
		int keys[] = { 20, 8, 22, 4, 12, 10, 14 };

		for (int x : keys)
			root = insert(root, x);

		int k = 4;
		Node res = kthSmallest(root, k);
		if (res == null)
			System.out.println("There are less than k nodes in the BST");
		else
			System.out.println("K-th Smallest Element is " + res.data);
	}
}

PreorderConstruction.java

class Solution {
  public TreeNode bstFromPreorder(int[] preorder) {
    int n = preorder.length;
    if (n == 0) return null;

    TreeNode root = new TreeNode(preorder[0]);
    Deque<TreeNode> deque = new ArrayDeque<TreeNode>();
    deque.push(root);

    for (int i = 1; i < n; i++) {
      TreeNode node = deque.peek();
      TreeNode child = new TreeNode(preorder[i]);

      while (!deque.isEmpty() && deque.peek().val < child.val)
        node = deque.pop();

      if (node.val < child.val) node.right = child;
      else node.left = child;

      deque.push(child);
    }
    return root;
  }
}

SearchBST.java

class Solution {
  public TreeNode searchBST(TreeNode root, int val) {
    if (root == null || val == root.val) return root;

    return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
  }
}