Balanced Root Check

Easy

0/40

0 upvote

Problem statement

For a given Binary Tree of type integer, your task is to determine if the height of the root's left subtree is exactly equal to the height of the root's right subtree.

The height of a binary tree is the number of nodes on the longest path from its root node down to the farthest leaf node.

An empty tree (a null node) has a height of 0.

A tree with a single node has a height of 1.

You must implement a function that calculates the height of the left subtree and the right subtree and returns true if they are equal, and false otherwise.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first and only line of input contains the node data, all separated by a single space. The data is given in a level-order format. A value of -1 is used to indicate that a left or right child does not exist and will not be part of the node data.

Output Format:

The only line of output will be true or false.

Note:

You are not required to print anything explicitly. The runner code has already been configured to handle the input and print the output based on the boolean value returned by your function.

Sample Input 1:

1 2 3 -1 -1 -1 -1

Sample Output 1:

true

Explanation for Sample 1:

The left subtree (rooted at 2) has a height of 1.
The right subtree (rooted at 3) has a height of 1.
Since 1 == 1, the function returns true.

Sample Input 2:

1 2 3 -1 4 -1 -1 -1 -1

Sample Output 2:

false

Explanation for Sample 2:

The left subtree (rooted at 2) has a height of 2 (path 2 -> 4).
The right subtree (rooted at 3) has a height of 1.
Since 2 != 1, the function returns false.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

0 <= Number of nodes <= 10^4
-10^5 <= Node.val <= 10^5

Time Limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Balanced Root Check

Console