Recently, I have made many problems about binary search tree, and found that many problems are solved by using the properties of binary search tree, and the routines are almost the same. Here is a summary.

Properties of binary search tree

• If its left subtree is not empty, the value of all nodes on its left subtree is less than that of its root node
• If its right subtree is not empty, the value of all nodes on its right subtree is greater than that of its root node
• Its left and right subtrees are also binary search trees
• The middle order traversal of binary search tree is an ordered sequence from small to large

The first three points are the inevitable nature of solving binary search tree problems, and the last point is the common ideas for solving problems.

Two methods to solve binary tree problems:

I recursion

• Determine the incoming parameters and return values
• Determine termination conditions
• Determine which traversal method to use
• Processing single layer logic

When does a recursive function need a return value and when does it not

• Usually, you only need to judge whether there is a certain value in the binary tree or whether a certain condition is satisfied, that is, you only need to find the qualified value (just search an edge of the binary tree) to end the situation. You need to return the value, because you can return the conclusion as soon as you meet the condition
• When traversing the entire binary tree, the return value is generally not required

II Iterative method

• dfs (the first, middle and last three traversal methods) is solved with the help of stack
• bfs (sequence traversal) is solved by queue

application

The simplest is to find a value in the binary search tree

Recursive method:

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
    	if(root==null||root.val==val) return root;
    	if(root.val<val) return searchBST(root.right, val);
    	if(root.val>val) return searchBST(root.left, val);
        return null;
    }
}

Iterative method: (because of the nature of binary search tree, it can complete the iterative method without the help of stack or queue)

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
    	while(root!=null) {
    		if(root.val==val) return root;
    		else if(root.val<val) root=root.right;
    		else root=root.left;
    	}
    	return null;
    }
}

By means of the ordered sequence traversed by the middle order of the binary search tree, it is verified that the code chip is inserted here
Recursion:

class Solution {
	TreeNode pre=null;//Initially, it is used to record the first value of the ordered sequence, and later it is used to compare with the current value
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        boolean left=isValidBST(root.left);
        if(pre==null) {
        	pre=root;
        }
        else {
        	if(pre.val>=root.val) return false;
        	pre=root;
        }
        boolean right=isValidBST(root.right);
        return left&&right;
    }
}

Iteration:

class Solution {
	TreeNode pre=null;
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        Deque<TreeNode> stack=new LinkedList<TreeNode>();
        while(root!=null||!stack.isEmpty()) {
        	if(root!=null) {
        		stack.push(root);
        		root=root.left;
        	}
        	else {
        		root=stack.pop();
        		if(pre==null) {
        			pre=root;
        		}
        		else {
        			if(pre.val>=root.val) return false;
        			pre=root;
        		}
        		root=root.right;
        	}
        }
        return true;
    }
}

Or using the property of middle order ergodic order, the minimum value can only be generated by subtracting two adjacent elements of middle order ergodic order
Recursion:

class Solution {
	int ans;
	int pre;
	private void dfs(TreeNode root) {
		if(root==null) return;
		dfs(root.left);
		if(pre==-1) pre=root.val;
		else {
			ans=Math.min(ans, Math.abs(root.val-pre));
			pre=root.val;
		}
		dfs(root.right);
	}
    public int getMinimumDifference(TreeNode root) {
    	pre=-1;
    	ans=Integer.MAX_VALUE;
    	dfs(root);
    	return ans;
    }
    
}

Iteration:

class Solution {
    public int getMinimumDifference(TreeNode root) {
    	int pre=-1;
    	int ans=Integer.MAX_VALUE;
    	Deque<TreeNode> stack=new LinkedList<TreeNode>();
    	while(root!=null||!stack.isEmpty()) {
    		while(root!=null) {
    			stack.push(root);
    			root=root.left;
    		}
    		root=stack.pop();
    		if(pre==-1) pre=root.val;
    		else {
    			ans=Math.min(ans, Math.abs(root.val-pre));
    			pre=root.val;
    		}
    		root=root.right;
    	}
    	return ans;
    }
    
}

Recursion:

class Solution {
	int maxcount;
	int count;
	TreeNode pre=null;
	List<Integer> list=new LinkedList<Integer>();
	void traversal(TreeNode root) {
		if(root==null) return ;
		traversal(root.left);
		if(pre==null) count=1;
		else if(root.val==pre.val) count++;
		else count=1;
		pre=root;
		if(count==maxcount) //Multiple modes
			list.add(root.val);
		if(count>maxcount) {//Maximum update
			list.clear();//All previously saved modes are invalid and empty
			list.add(root.val);
			maxcount=count;
		}
		traversal(root.right);
		
	}
    public int[] findMode(TreeNode root) {
    	maxcount=0;
    	count=0;
    	traversal(root);
    	int res[]=new int[list.size()];
    	for(int i=0;i<list.size();i++)
    		res[i]=list.get(i);
    	return res;
    }
}

Iteration:

class Solution {
	int maxcount;
	int count;
	TreeNode pre=null;
	List<Integer> list=new LinkedList<Integer>();
    public int[] findMode(TreeNode root) {
    	maxcount=0;
    	count=0;
    	Deque<TreeNode> stack=new LinkedList<TreeNode>();
    	while(root!=null||!stack.isEmpty()) {
    		if(root!=null) {
    			stack.push(root);
    			root=root.left;
    		}
    		else {
    			root=stack.pop();
    			if(pre==null) count=1;
    			else if(root.val==pre.val) count++;
    			else count=1;
    			pre=root;
    			if(count==maxcount) 
    				list.add(root.val);
    			if(count>maxcount) {
    				list.clear();
    				list.add(root.val);
    				maxcount=count;
    			}
    			root=root.right;
    		}
    	}
    	int res[]=new int[list.size()];
    	for(int i=0;i<list.size();i++)
    		res[i]=list.get(i);
    	return res;
    }
}

From the above questions, we can draw a rule that binary search tree questions are often solved with the help of the property of ordered ergodic order. Usually, a pre is defined, and the initial value is empty or - 1 (depending on the specific definition). By comparing pre with the current node, we can judge whether it conforms to the property of ordered ergodic order, so as to solve the problem.