Java/Ch 04. Trees and Graphs/Q4_05_Validate_BST/Question.java

[sangnguyen7]

You're solution is great. But I found a small issue, please correct me if I was wrong. Suppose, we have a tree as below: 4
/ \
2 6
/ \ / \ 1 3 4 7

Based on the problem stated, it is supposed to return "false" in this case. However, the code returned "true".

[hiteshi27]

Hello, Kindly checkout my solution here: https://github.com/hiteshi27/Cracking-The-Coding-Interview-6-JAVA/blob/master/chapter4_trees_and_graphs/q5_ValidateBST.java

[sangnguyen7]

Hi Hiteshi27,

Thanks for sharing! Yes, the solution you're sharing is absolutely working for my case. Actually, in this repository also has that solution already (CtCI-6th-Edition/Java/Ch 04. Trees and Graphs/Q4_05_Validate_BST/QuestionB.java). However, my question is for the solution in Q4_05_Validate_BST/Question.java.

[augustomelo]

Yeah a believe the problem is in this part: https://github.com/careercup/CtCI-6th-Edition/blob/ee6781560cb61c12a2b8cc3ef3493de3891d82c2/Java/Ch%2004.%20Trees%20and%20Graphs/Q4_05_Validate_BST/Question.java#L27

How the left most item will be greater than the root ? I believe the correct why to check is: if (n.data > last_printed)

[mcsimk]

I recon the reason this happens is because

				// Right child "is not allowed" be equal to parent.
				if (n.data <= lastPrinted) {
					return false;
				}

is missing one additional check. For every node algorithm should verify:

• left branch items are all less or equal than current node - this is being verifed
• right branch items are all greater than current node - this is verified verified before visiting right branch implying than if any of the right branch items is smaller than current node it will detect and propagate up
• neither node itself nor any of its children can be smaller than parent - this is not verified, e.g. you could save lastVisited first thing in the function, then after visiting both left and right branches compare lastVisited to saved value

[hobossa]

I found a similar issue. create tree from int[] {1,2,3,3,3,4,5} , as the follow shows. It should not return true. ..........3 ...2..........4 1...3......3...5

[hobossa]

In this fix the bug?
https://github.com/hobossa/cc189/blob/main/proj/src/main/java/CH04_TreesAndGraphs/ValidateBST/ValidateBST_v3.java

Using a static int variable to record the last element's depth. // traverse the tree using an in-order traversal (left, current, right). // there are two scenarios continuously alternating here. Using a static int variable to record the last element's depth. // 1, the last Element is on the current node's left child tree. the last element' depth should greater than current depth // the last element should not be greater than the current // 2. current element is on the last Element's right child tree. the last element's depth should smaller than current depth. // the last element should not be greater than or equal to the current