CODEWITHSUNDEEP
algorithmbinary-search-tree
William
William

Reputation: 449

Binary tree validation

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?

Upvotes: 4

Views: 476

Answers (1)

Am_I_Helpful
Am_I_Helpful

Reputation: 19178

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.

Upvotes: 3

Related Questions