binary search tree

[Ning2018]

Inorder: left, middle, right, the order is small to large Preorder: middle, left, right Postorder: left, right, middle

[Ning2018]

size of BST: the number of nodes in BST depth of BST: the number of edge layers

[Ning2018]

DFS: depth first search

List vals; vals = new ArrayList<>(); dfs(TreeNode node){ if(node==null) return; vals.add(node.val); dfs(node.left); dfs(node.right); }

[Ning2018]

package LeeCode;

import java.util.Collection;

public class BST {

// TreeNode tree= new TreeNode(20,null,null); BST(){

}
BST(int[] nums, TreeNode tree){
    for(int i:nums) {
        tree.add(i);
    }
}

Integer ans = Integer.MAX_VALUE;
TreeNode prev = new TreeNode(-1,null,null);

public static void main(String[] args) {
    // TODO Auto-generated method stub

    TreeNode root = new TreeNode(6,null,null);
    int[] nums = new int[] {4,1,5,7,9};
    BST bst = new BST(nums, root);
    bst.dfs(root);
    root.traverseInOrder();

}

public void dfs(TreeNode node) {

    if(node == null) return;
    dfs(node.left);
    if(prev!=null) {
        ans= Math.min(ans, node.val-prev.val);
    }
    prev.val=node.val;
    dfs(node.right);
}

}

class TreeNode {

int val;
TreeNode left;
TreeNode right;
TreeNode(int x,TreeNode left,TreeNode right){
    val = x;
    this.left =left;
    this.right =right;
}

public void traverseInOrder() {
    // TODO Auto-generated method stub
    if(this.left!=null) {
        this.left.traverseInOrder();
    }
    System.out.println(this.val);
    if(this.right!=null) {
        this.right.traverseInOrder();
    }
}

void add(int i) {
    if(i<this.val) {
        if(this.left==null) {
            this.left = new TreeNode(i,null,null);
        }
        else {
            this.left.add(i);
        }
    }
    else {
        if(this.right==null) {
            this.right= new TreeNode(i,null,null);
        }
        else {
            this.right.add(i);
        }
    }
}

}

[Ning2018]

output: 1 4 5 6 7 9