DS: Trees
Written:
Data Structure: A review article on some concept of trees. *This is a series of articles on basic data structures*
A tree is a collection of nodes connected by directed (or undirected) edges.
Acyclic
A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures.
A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees.
If a given tree has n nodes, it has n-1 edges
public class TreeNode {
public int key;
public TreeNode left;
public TreeNode right;
public TreeNode(int key) {
this.key = key;
}
}
Some concepts:
1. Height: the height of a node is the number of edges from that node to the deepest leaf.
public int height(TreeNode root){
if(root == null){
return 0;
}
int left = height(root.left);
int right = height(root.right);
return Math.max(left, right)+1;
}
//Time complexity: O(n), if balanced O(height)
//Space complexity: O(height)
2. Depth: the depth of a node is the number of edgees from the root to that node.
//depth of a certain node
//Assumption: the node is in the tree
public int depth(TreeNode root, TreeNode target){
if(root == null) {return -1;}
return depth(root, target, 1);
}
private int depth(TreeNode root, TreeNode target, int level){
if(root == null){
return 0;
}
if(root == target) {
return level;
}
int result = 0;
result = depth(root.left, target, level+1);
//case 1: found in left subtree
if(result != 0) {
return result;
}
//case 2: found in right subtree
result = depth(root.right, target, level+1);
if(result != 0) {
return result;
}
return -1;
}
3. Balanced tree: for each node, the heights difference of its left subtree and right subtree is no larger than 1.
// Solution 1: Top down solution (use its definition, check the balances of left and right subtree, as well as itself)
// Time complexity: O(nlogn) = logN(main function) * n(get height)
// Space complexity: O(n)
pulic boolean isBalanced(TreeNode root){
if(root == null) {
return true;
}
int left = getHeight(root.left);
int right = getHeight(root.right);
if(Math.abs(left-right) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
private int getHeight(TreeNode root){
//Time complexity: O(n), if balanced O(height)
//Space complexity: O(height)
if(root == null){
return 0;
}
int left = height(root.left);
int right = height(root.right);
return Math.max(left, right)+1;
}
//Solution 2: Bottom-up solution (Check its balance when getting its height, and return height if balanced)
//Time complexity: O(n), if balanced O(height)
//Space complexity: O(height)
pulic boolean isBalanced(TreeNode root){
return isBalanced(root) != -1;
}
private int isBalanced(TreeNode root){
// returns height of current node if all its subtrees including itself is balanced, otherwise return -1.
if(root == null){
return 0;
}
int left = height(root.left);
int right = height(root.right);
if(left == -1 || right == -1 || Math.abs(left-right) > 1){
return -1;
}
return Math.max(left, right)+1;
}
4. Compelete tree: Except the last level, nodes on other levels are fully filled. The nodes on the last level are as left as possible. <=> if we meets bubble/null nodes, the rest of nodes should all be null.
// Complete Tree == if we meet a null node, rest of nodes all have to be null.
public boolean isComplete(TreeNode root){
if(root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
boolean meetNull = false;
queue.offer(root);
while(queue.isEmpty()){
TreeNode curr = queue.poll();
//case 1: check left subtree, check if left tree is null?
// if meetNull, then rest of them have to be null, otherwise return false.
if(curr.left != null){
if(meetNull){
return false;
}
queue.offer(curr.left);
} else {
meetNull = true;
}
//case 2: check right subtree, check if right tree is null?
// if meetNull, then rest of them have to be null, otherwise return false.
if(curr.right != null){
if(meetNull){
return false;
}
queue.offer(curr.right);
} else {
meetNull = true;
}
}
return true;
}
5. Full tree: for each node, it has either no children or two children.
//Time complexity: O(height)
//Space complexity: O(height)
public boolean isFull(TreeNode root){
if(root == null) {
return true;
}
if(root.left == null && root.right == null){
return true;
}
if(root.left != null && root.right != null){
return isFull(root.left) && isFull(root.right);
}
return false;
}
Tree Traversal:
- PreOrder
//C++ code
//Data structure: Stack
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> stk;
if (root==NULL) return result;
stk.push(root);
while (!stk.empty()) {
root = stk.top();
result.push_back(root->val);
stk.pop();
if(root->right != NULL){
stk.push(root->right)
};
if(root->left != NULL){
stk.push(root->left)
};
}
return result;
}
- InOrder
//C++ code
//Data structure: Stack
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
if (root == NULL) return result;
stack<TreeNode*> stk;
stk.push_back(root);
TreeNode* currNode =root->left;
while(currNode !=NULL) {
stk.push(currNode);
currNode = currNode->left;
}
while (!stk.empty()){
currNode = stk.top();
stk.pop();
result.push(currNode->val);
currNode = currNode->right;
while(currNode!=NULL){
stk.push(currNode);
currNode = currNode->left;
}
}
return result;
}
- PostOrder
//JAVA code
//Data structure: Stack
public List<Integer> postOrder(TreeNode root){
List<Integer> res = new ArrayList<>();
//sanity check
if(root == null){
return res;
}
Deque<TreeNode> stack = new ArrayDeque<>();
stack.offerLast(root);
TreeNode prev = null;
while(!stack.isEmpty()){
TreeNode curr = stack.peekLast();
if(prev == null || curr == prev.left || curr == prev.right){//case 1: curr == root || going down
if(curr.left != null){
stack.offerLast(curr.left);
} else if(curr.right != null){
stack.offerLast(curr.right);
} else{
stack.pollLast();
res.add(curr.val);
}
} else if (prev == curr.left){ // case2: going up from left subtree
if(curr.right != null){
stack.offerLast(curr.right);
}
} else { //case 3: going up from right subtree or no right subtree
stack.pollLast();
res.add(curr.val);
}
prev = curr;
}
return res;
}
- LevelOrder
//JAVA Code
//Data structure: Queue
public List<List<Integer>> levelOrder(TreeNode root){
List<List<Integer>> result = new ArrayList<>();
if(root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> currLevel = new ArrayList<>();
int size = queue.size();
for(int i = 0; i< size; i++) {
TreeNode curr = queue.poll();
result.add(curr.val);
if(curr.left != null) {
queue.offer(curr.left);
}
if(curr.right != null) {
queue.offer(curr.right);
}
}
result.add(currLevel);
}
return result;
}
Binary Seach Tree:
- For each node, nodes in the left subtree are smaller than the current root, and nodes in the right subtree are larger than the current root.
- BST Inorder traversal: ascending order.
- Determine if a binary tree is binary search tree?
public boolean isBST(TreeNode root){
if(root == null){
return true;
}
return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean isBST(TreeNode root, int leftBound, in rightBound){
if(root == null){
return true;
}
if(root.val <= leftBound || root.val >= rightBound){
return false;
}
return isBST(root.left, leftBound, root.val) && isBST(root.right, root.val, rightBound);
}
- In a BST, find node with cloest value to the target.
//Recursive Solution
//Time complexity: O(height)
//Space complexity: O(height)
public TreeNode cloestTreeNode(TreeNode root, int target){
if(root == null){
return null;
}
TreeNode next = root.key < target ? root.right : root.left;
if(next == null) {return root;}
TreeNode curr = cloestTreeNode(next, target);
return Math.abs(curr.key - target) < Math.abs(root.key - target)? curr : root;
}
//Iterative Solution
//Time complexity: O(height)
//Space complexity: O(1)
public TreeNode cloestTreeNode(TreeNode root, int target){
if(root == null){
return null;
}
TreeNode result = root;
while(root != null){
if(root.key == target){
return root;
}
result = Math.abs(root.key - target) < Math.abs(result - target) ? root : result;
root = root.key < target ? root.right : root. left;
}
return result;
}
- In a BST, find largest number smaller than target.
//Iterative Solution
//Time complexity: O(height)
//Space complexity: O(1)
public TreeNode cloestTreeNode(TreeNode root, int target){
if(root == null){
return null;
}
TreeNode result = null;
while(root != null){
if(root.key < target){//go to the right
result = root;
root = root.right;
} else {
root = root. left;
}
}
return result;
}
- Two Sum on BST.
Solution 1: populate a sorted array with inorder traversal and do 2Sum on it
- Time complexity: o(n+n)
- Space complexity: O(n)
Solution 2: use BST iterator to iterate the BST and do 2Sum.
- Time complexity: o(n)
- Space complexity: O(1)
Breath First Search Topological Sorting