Leaf at same level in binary tree

Question

Given a Binary Tree, check if all leaves are at same level or not.

Input:

Output: 0

Explanation: Leaves 10, 15 and 30 are not at same level.
Approach: The height of left subtree and right subtree should be same for each node.

My Code:

int height(Node* root){
    if(root == NULL) return 0;
    return 1 + max(height(root->left), height(root->right));
}
bool check(Node *root)
{
    if(root == NULL) return true;
    if(root->left == NULL && root->right == NULL) return true;
    if(root->left == NULL || root->right == NULL) return false;
    int l = height(root->left);
    int r = height(root->right);
    if(l == r) return true;
    return false;
    
}

ISSUE: This code doesn't work for multiple test cases though. Can someone help me figure out why?

Testcase failed:
2910 7670 N 712 4700 N 8459 2271 N 332 8570 N 7403 8390 N 9496 8400 N 8771 6683 N 1647 440 N 1979 1254

Its Correct output is: 1

And my Code's output is: 0

String Representation:

what test cases fail? Please include a minimal reproducible example, input, output and expected output in the question — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Feb 3, 2021 at 12:07
So in your failing example, what are the values of height(root->left) and height(root->right)? And what should they be? — Useless
– Useless, Commented Feb 3, 2021 at 12:13
so far, question improved a lot, minimal reproducible example is still missing though — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Feb 3, 2021 at 12:13
According to testcase and string representation it should be 0. — amar_1995
– amar_1995, Commented Feb 3, 2021 at 12:21
@kaba maybe its a matter of wording, but "Generally, AFAIK, it is discouraged to compare a pointer to anything other than nullptr" is not right. Eg there is absolutely no problem to have two pointers and compare them via a == b (even if none of them is a nullptr) — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Feb 3, 2021 at 13:05

Caleth · Accepted Answer · 2021-02-03 12:39:41Z

3

You are only checking that the deepest leaf to the left of root is at the same height as the deepest leaf to the right of root. You need to check the minimum height against the maximum height.

std::pair<int, int> heights(Node * node) {
    if (node->left && node->right) {
        auto [lmin, lmax] = heights(node->left);
        auto [rmin, rmax] = heights(node->right);
        return { 1 + std::min(lmin, rmin), 1 + std::max(rmax, lmax) };
    } else if (node->left) {
        auto [min, max] = heights(node->left);
        return { 1 + min, 1 + max };
    } else if (node->right) {
        auto [min, max] = heights(node->right);
        return { 1 + min, 1 + max };
    } else {
        return { 0, 0 };
    }
}

bool check(Node * node) {
    auto [min, max] = heights(node);
    return min == max;
}

edited Feb 3, 2021 at 12:39

answered Feb 3, 2021 at 12:26

Caleth

66k2 gold badges53 silver badges101 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Leaf at same level in binary tree

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related