3

I'm newbie in Python and I've some problem. I'm using Python 3.

I've used this logic for binary search trees to get the height of it:

class Node:
    def __init__(self, data):
        self.right = self.left = None
        self.data = data


class Solution:
    def insert(self, root, data):
        if root is None:
            return Node(data)
        else:
            if data > root.data:
                cur = self.insert(root.right, data)
                root.right = cur
            else:
                cur = self.insert(root.left, data)
                root.left = cur
        return root

    def getHeight(self, root):
        # Write your code here
        if root is None:
            return 0
        else:
            return 1 + max(self.getHeight(root.right), self.getHeight(root.left))

T = int(input())
myTree = Solution()
root = None
for i in range(T):
    data = int(input())
    root = myTree.insert(root, data)

height = myTree.getHeight(root)
print(height)

With this input:

7
3
5
2
1
4
6
7

The first 7 is the number of nodes.

But I got four instead of three and in the example it is said that the height must be three.

What I am doing wrong?

NOTE: my code is only on getHeight method.

1
  • I think 4 is the correct answer here. Commented Sep 3, 2017 at 9:43

1 Answer 1

1

You can hand-check your answer by drawing the tree based on the insert logic

level1             3
level2         2       5
level3     1         4   6
level4                     7

If you are counting edges, then yes, it's three, but the height of the tree is clearly four.

You can hack around the poorly worded problem by return -1 in the base case

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

5 Comments

The first 7 is the number of nodes.
As you can see here as well, the height is actually 4 not 3.
Look: hackerrank.com/challenges/30-binary-search-trees/problem. This is the problem statement. Here they want to count the edges not the nodes.
The edges is not equal to the height
@VansFannel return -1 instead of 0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.