Leetcode Some problems about Binary Search Tree

173. Binary Search Tree Iterator

Description

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.

Answer

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

Description

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.

Answer

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

Description

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

Answer

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 *