Challenge: How Tall Is the Tree?

Lab Java Beginner 10 points

Read a binary tree and print its height – the number of levels (a single node has height 1).

Input

Line 1: n, the number of nodes (numbered 0 to n − 1; node 0 is the root). Then n lines, one per node in order: value left right, where left and right are child node numbers, or -1 for no child.

Output

The height.

Example

Input

Output

Sample input available Sample output available

Editor

Java

Hints

height(null) = 0.

height(node) = 1 + the taller of the two subtrees.

Solution explanation

O(n). Notice the last test: a tree where every node has only a right child is really a linked list, and its height is n.

Show solution

import java.util.Scanner;

class TreeNode {
    int value;
    TreeNode left, right;
    TreeNode(int value) { this.value = value; }
}

public class Main {
    static TreeNode[] build(Scanner sc) {
        int n = sc.nextInt();
        TreeNode[] nodes = new TreeNode[n];
        int[] left = new int[n], right = new int[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new TreeNode(sc.nextInt());
            left[i] = sc.nextInt();
            right[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            if (left[i] != -1) nodes[i].left = nodes[left[i]];
            if (right[i] != -1) nodes[i].right = nodes[right[i]];
        }
        return nodes;
    }

    static int height(TreeNode n) {
        if (n == null) return 0;
        return 1 + Math.max(height(n.left), height(n.right));
    }

    public static void main(String[] args) {
        TreeNode root = build(new Scanner(System.in))[0];
        System.out.println(height(root));
    }
}

Output

Answer