CodingGyan

Binary Search Tree: Insert, Inorder and Height

medium Data Structures and Algorithms

Problem

Insert the numbers into an empty binary search tree in the given order (a number that is already in the tree is ignored). Print two lines: inorder: with the values of an inorder walk, and height: with the number of levels of the tree (an empty tree has height 0; one node has height 1).

Constraints

  • 1 <= n <= 2000

Examples

Input

5
5 3 8 1 4

Output

inorder: 1 3 4 5 8
height: 3

Solutions

Best approachTime O(n * h)Space O(n)

Inorder of a BST is always sorted, so building the tree and walking it is a sort. The height depends on the order of the input: sorted input gives a very tall tree (height n), which is why balanced trees exist.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Build a BST.
 * Input   : n, then n integers.
 * Output  : Two lines.
 * Approach: Recursive insert.
 * Time    : O(n * h)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: A BST node keeps a value and two children. Smaller values go left. Bigger values go right.
        static class Node {
            int value;
            Node left;
            Node right;

            Node(int value) {
                this.value = value;
            }
        }

        // Step 2: Insert by walking down. A value that is already in the tree is ignored.
        static Node insert(Node node, int value) {
            if (node == null) {
                return new Node(value);
            }
            if (value < node.value) {
                node.left = insert(node.left, value);
            } else if (value > node.value) {
                node.right = insert(node.right, value);
            }
            return node;
        }

        // Step 3: Inorder (left, node, right) gives the values in sorted order.
        static void inorder(Node node, StringBuilder text) {
            if (node == null) {
                return;
            }
            inorder(node.left, text);
            text.append(text.length() == 0 ? "" : " ").append(node.value);
            inorder(node.right, text);
        }

        // Step 4: The height is the number of nodes on the longest path from the root down.
        static int height(Node node) {
            if (node == null) {
                return 0;
            }
            return 1 + Math.max(height(node.left), height(node.right));
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(int[] a) {
        // Step 5: Insert all numbers one by one. The root can change only for the first number.
        Node root = null;
        for (int value : a) {
            root = insert(root, value);
        }

        // Step 6: Read the sorted values and the height.
        StringBuilder text = new StringBuilder();
        inorder(root, text);
        return new String[] {"inorder: " + text, "height: " + height(root)};
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(String.join("\n", solve(a)));
    }
}
Hints (1)
  1. Why is the inorder walk sorted?

Try these next