Given the root node of a **Binary Tree**, write a method - **iteratively** determine if it is a Binary **Search** Tree.

**A BST must satisfy the following conditions :**

* The left subtree of a node contains nodes with data < its data.

* The right subtree of a node contains nodes data > its data.

* A node's left and right subtrees follow the above two conditions.

**Examples:**

`validateBSTItr`

to * The left subtree of a node contains nodes with data < its data.

* The right subtree of a node contains nodes data > its data.

* A node's left and right subtrees follow the above two conditions.

20

/ \

15 30

/ \

14 18

output ==> true

20

/ \

30 15

/ \

14 18

output ==> false

Need a **hand?** Try out these hints, one at a time.

Carefully consider the properties that a BST node must follow. The key here is to use a

`Queue`

to do a level order traversal of a tree that is constructed using a special local class that stores all properties of a `TreeNode`

, but also stores the max and min ranges that a `TreeNode`

's value must lie within
1. Create a local class

2. Create a

3. Add the root node of the Tree to the

4. While the

5. If the

6. Otherwise, if the

7. If the

8. At the end of the while loop, return

`TreeBoundaryNode`

that stores the corresponding `TreeNode`

, and two integers - `leftBoundary`

and `rightBoundary`

.2. Create a

`Queue`

of `TreeBoundaryNode`

that will be used to perform a standard level order traversal.3. Add the root node of the Tree to the

`Queue`

with an infinite range boundary - `q.add(new TreeBoundaryNode(`

`root,`

`Integer.MIN_VALUE, `

`Integer.MAX_VALUE));`

4. While the

`Queue`

is not empty, perform a standard level order traversal. 5. If the

`data`

of the node in the current `TreeBoundaryNode`

lies outside the ranges defined by the `TreeBoundaryNode`

's `leftBoundary`

and `rightBoundary`

, return `false`

.6. Otherwise, if the

`left`

`TreeNode`

is not `null`

, create and add a new `TreeBoundaryNode`

like this : `q.add(new TreeBoundaryNode(`

`t.left, `

`tbNode.leftBoundary, `

`t.data));`

7. If the

`right`

`TreeNode`

is not `null`

, create and add a new `TreeBoundaryNode`

like this : `q.add(new TreeBoundaryNode(`

`t.right, `

`t.data, `

`tbNode.rightBoundary));`

8. At the end of the while loop, return

`true`

public static boolean validateBSTItr(TreeNode root) { }

**C**

**Java**

**Python**