Leetcode Some problems about Binary Search Tree

173. Binary Search Tree Iterator


Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.


We need a Stack to help us to save the next smallest number.

In a Binary Search Tree, The most left node is the minimum. So we can save each left node from root in a stack and get the minimum left node.
So the function hasNext() just return !stack.isEmpty();
And every time we use next(),we pop the stack, and push all left nodes of the pop node’s right node.
So code is following.

98. Validate Binary Search Tree


Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Example 1:

Binary tree [2,1,3], return true.
Example 2:

Binary tree [1,2,3], return false.


The basic method is to use a inorder traversal, because in a BST the left always less than the right.

I design a recursion to solve the problem.

108. Convert Sorted Array to Binary Search Tree


Given an array where elements are sorted in ascending order, convert it to a height balanced BST


With what I said above, BST owns its special character, left < right. So the middle of the sorted array must be the root of BST.
At the same time, the root of any child subtree must the middle number of part array. So I can use a recursion function to solve it.

Leave a Reply

Your email address will not be published. Required fields are marked *