4

Been working through some of Hacker Ranks Cracking the Coding Interview problems and just recently got to this one: Binary Tree Problem.

In the problem description, the author goes over what is considered to be a valid binary tree.

"The value of every node in a node's left subtree is less than the data value of that node."

However they mention that this tree

enter image description here

is valid. But by their description of a valid binary search tree, wouldn't this tree be invalid because Node 4 has a left child of Node 5, which is greater. Or am I misunderstanding what makes a valid BST?

Improve this question
1
  • 4
    You're correct. This isn't a valid binary search tree. Commented Jul 8, 2018 at 2:13

1 Answer 1

Reset to default
3

Q: But by their description of a valid binary search tree, wouldn't this tree be invalid because Node 4 has a left child of Node 5, which is greater. Or am I misunderstanding what makes a valid BST?

A: You're correct. The image and the line they state are contradicting each other in this case.

The author has clearly stated the following definition for a valid BST:

For the purposes of this challenge, we define a binary search tree to be a binary tree with the following properties:

  1. The data value of every node in a node's left subtree is less than the data value of that node.

  2. The data value of every node in a node's right subtree is greater than the data value of that node.

  3. The data value of every node is distinct.

Hence, the tree in the image doesn't qualify as a valid BST.

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

Comments

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.