Skip to content

Tree Summary

Jump to bottom
Xin Wan edited this page Jun 21, 2018 · 8 revisions

Binary Tree, Binary Search Tree -> General Tree -> Graph

Tree concepts

  • balanced tree: The constraint is generally applied recursively to every subtree. That is, the tree is only balanced if:
    • The left and right subtrees' heights differ by at most one, 2.
    • The left subtree is balanced, AND
    • The right subtree is balanced
  • complete tree: a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
  • full tree: A Binary Tree is full if every node has 0 or 2 children. In a Full Binary, number of leaf nodes is number of internal nodes plus 1.
  • perfect tree: A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level. A Perfect Binary Tree of height h (where height is number of nodes on path from root to leaf) has 2h – 1 node.
  • depth: The depth of a node is the number of edges from the node to the tree's root node. A root node will have a depth of 0.
  • height: The height of a node is the number of edges on the longest path from the node to a leaf. A leaf node will have a height of 0.
  • binary search tree

Tree Traversal

Inorder Traversal

  1. Recursion:
    • Pros: elegant
    • Cons: stack space
private List<Integer> inorderTraversalByRecursion(TreeNode root) {
        if (root == null) {
            return new ArrayList<Integer>();
        }
        
        List<Integer> result = new ArrayList<Integer>();
        
        result.addAll(inorderTraversal(root.left));
        result.add(root.val);
        result.addAll(inorderTraversal(root.right));
        return result;
    }
  1. Iteration way
private List<Integer> inorderTraversalByIteration(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            if (cur == null) {
                cur = stack.pollFirst();
                result.add(cur.val);
                cur = cur.right;
            }
            
            while (cur != null) {
                stack.offerFirst(cur);
                cur = cur.left;
            }
        }
        
        return result;
    }
  • Time: O(n)
  • Space: O(hight)
  1. Iterator way
private class InorderIterator {
        Deque<TreeNode> stack;
        
        public InorderIterator(TreeNode root) {
            stack = new ArrayDeque<TreeNode>();
            push(root);
        }
        
        public boolean hasNext() {
            return stack.size() != 0;
        }
        
        public int next() {
            TreeNode cur = stack.pollFirst();
            int val = cur.val;
            push(cur.right);
            
            return val;
        }
        
        public void push(TreeNode node) {
            while (node != null) {
                stack.offerFirst(node);
                node = node.left;
            }
        }
    }
    
    private List<Integer> inorderTraversalByIterator(TreeNode root) {
        InorderIterator it = new InorderIterator(root);
        List<Integer> result = new ArrayList<Integer>();
        while (it.hasNext()) {
            result.add(it.next());
        }
        return result;
    }

Iterator Applications:

  • The iterator will provide a sequence view of the original binary tree.
  • Inorder sequence view is especially useful for BST --> It is a sorted sequence
  • Grouping the traversal logic in a delegated place for better coding / logic structure.
  • Second largest node in the given BST -> The second traversing node in reverse inorder (right->root->left)

Good questions:

Binary Tree and Binary Search Tree

  • Trick: base case usually refers to the NULL ChildNode below the leaf node
public void preOrder(TreeNode root) {
    if (root == null) return;
    System.out.println("x");
    preOrder(root.left);
    preOrder(root.right);
}
  • Balanced binary tree is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less.
  • Complete binary tree: is a binary tree in which every level, except possibly the last, is completed filled, and all nodes are as far left as possible.
  • Binary Search Tree: for every single node in the tree, the values in its left subtree are all smaller than its value, and the values in its right substree are all larger than its value.

questions:

  • binary search tree rethink (search, insert, delete)
  • Tree traversal rethink (in/pre/post-order): recursive, iterative iterator
  • DFS rethink (recursion - not using side effect, backtracking - utilizing side effect , traversal)
  • rethink divide conquer (root, root.left, root.right, 顺序 in／post/pre-order)

Clone this wiki locally