Data Structure: Tree and its Traversal
Tree
A tree is a widely used data structure that represent a hierarchical structure with a set of connected nodes.
Each node in the tree can be connected to many children (depending on the type of tree), but must be connected to exactly one parents.
This constraint means that there are no cycles or “loops”, also each child can be treated like the root node of its own subtree.
so the definition of tree node should looks like
public class Node {
int val;
Node left;
Node right;
public Node(int i) {
val = i;
}
}
This article, I will represent several typical algorithm problems relating to Tree.
Tree Traversal
Traversal problem is the most common problem relating to trees, based on the order wise of traverse, it can be categorized by pre-order traversal, mid-order traversal and post-order traversal, each traversal can implemented by either iteration way or recursive way
pre-order traversal
in pre-order traversal, we first process the root node of each subtree, then process its left child-tree, then right child-tree.
public class PreorderTraversal {
public void recurTraverse(Node root) {
if (root == null) {
return;
}
System.out.println(root.val); // can customize the logic on each node
recurTraverse(root.left);
recurTraverse(root.right);
}
public void iterTraverse(Node root) {
Stack<Node> stack = new Stack<>();
Node cur = root;
while(cur != null) {
System.out.println(cur.val); // can customize the logic on each node
stack.push(cur);
cur = cur.left;
while (cur == null && !stack.isEmpty()) {
cur = stack.pop();
cur = cur.right;
}
}
}
}
mid-order traversal
int mid-order traversal, for each node, process its left child-tree first, then process the node itself, then process its right child-tree.
public class MidorderTraversal {
public void recurTraverse(Node root) {
if (root == null) {
return;
}
recurTraverse(root.left);
System.out.println(root.val); // can customize the logic on each node
recurTraverse(root.right);
}
public void iterTraverse(Node root) {
Stack<Node> stack = new Stack<>();
while(root != null) {
stack.push(root);
root = root.left;
}
while(!stack.isEmpty()) {
root = stack.pop();
System.out.println(root.val); // can customize the logic on each node
root = root.right;
while(root != null) {
stack.push(root);
root = root.left;
}
}
}
}
post-order traversal
in post order traversal, for each node, first process its left subtree, then process its right subtree, finally process node itself.
public class PostorderTraverse {
public void recurTraverse(Node root) {
if (root == null) {
return;
}
recurTraverse(root.left);
recurTraverse(root.right);
System.out.println(root.val); // logic can be customized
}
public void iterTraverse(Node root) {
Stack<Node> res = new Stack<>();
Stack<Node> stack = new Stack<>();
while(root != null) {
res.push(root);
stack.push(root);
root = root.right;
while (root == null && !stack.isEmpty()) {
root = stack.pop();
root = root.left;
}
}
while(!res.isEmpty()) {
root = res.pop();
System.out.println(root.val);
}
}
}
Level-based Traverse
Besides the 3 typical traversal mentioned above, there is another common traversal way which is level based traverse.
public class LevelTraverse {
public void traverse(Node root) {
Queue<Node> queue = neW Linkedlist<>();
queue.add(root);
Node cur;
while(!queue.isEmpty()) {
cur = queue.poll();
System.out.println(cur.val); // logic can be customized here
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
}
}
Tree Width Problem
There is another problem which can be solved by level-based traversal, which is measure the width of a tree.
public class TreeWidth {
public int getTreeWidth(Node root) {
Node nextEnd = root, curEnd = root;
Node cur;
int maxWidth = 0, curWidth = 0;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
cur = queue.poll();
if (cur.left != null) {
nextEnd = cur.left;
queue.push(cur.left);
}
if (cur.right != null) {
nextEnd = cur.right;
queue.push(cur.right);
}
curWidth++;
if (cur == curEnd) {
if (curWidth > maxWidth) {
maxWidth = curWidth;
}
curWidth = 0;
curEnd = nextEnd;
}
}
}
}
Serialization
When you say the tree traversal, you cannot ignore the serialization of overall tree.
pre-order serialization
public class PreOrderSerializer {
public static String serialize(Tree root) {
StringBuilder sb = new StringBuilder();
process(root, sb);
return sb.toString();
}
private static void process(Node root, StringBuilder sb) {
if (root == null) {
sb.append(",null");
return;
}
sb.append(",");
sb.append(root.val);
process(root.left, sb);
process(root.right, sb);
}
public static Node deSerialize(String input) {
String[] split = input.split(",");
Queue<String> queue = new LinkedList<>();
for(String s: split) {
queue.add(s);
}
return build(queue);
}
private static Node build(Queue<String> queue) {
String cur = queue.poll();
if(cur.equals("null")) {
return null;
}
Node head = new Node(Integer.valueOf(cur));
head.left = build(queue);
head.right = build(queue);
return head;
}
}
mid-order serialization
unfortunately mid-order serialization cannot uniquely determine a tree.
post-order serialization
public class PostOrderSerializer {
public String serialize(Node root) {
StringBuilder sb = new StringBuilder();
build(root, sb);
return sb.toString();
}
private void build(Node root, StringBuilder sb) {
if (root == null) {
sb.append(",null");
return;
}
build(root.left, sb);
build(root.right, sb);
sb.append(",");
sb.append(root.val);
}
public Node deSerialize(String input) {
String[] split = input.split(",");
Stack<String> stack = new Stack<>();
Node head = build(stack);
return head;
}
private Node build(Stack<String> stack) {
String curString = stack.pop();
if(curString.equals("null")) {
return null;
}
Node cur = new Node(Integer.valueOf(curString));
cur.right = build(stack);
cur.left = build(stack);
return cur;
}
}
level-order serialization
public class LevelOrderSerializer {
public static String serialize(Node head) {
StringBuilder sb = new StringBuilder();
Queue<Node> queue = new LinkedList<>();
queue.add(head);
sb.append(head.val);
Node cur;
while(!queue.isEmpty()) {
cur = queue.poll();
if (cur.left != null) {
queue.add(cur.left);
sb.append(",");
sb.append(cur.left.val);
} else {
sb.append(",null");
}
if (cur.right != null) {
queue.add(cur.right);
sb.append(",");
sb.append(cur.right.val);
} else {
sb.append(",null");
}
}
}
public static Node deSearialize(String input) {
String[] split = input.split(",");
Queue<String> queue = new LinkedList<>();
Queue<Node> nodeQ = new LinkedList<>();
for(String s: split) {
queue.add(s);
}
Node head = genNode(queue.poll());
nodeQ.add(head);
Node cur;
while(!nodeQ.isEmpty()) {
cur = nodeQ.pop();
cur.left = genNode(queue.poll());
cur.right = genNode(queue.poll());
if (cur.left != null) {
nodeQ.add(cur.left);
}
if (cur.right != null) {
nodeQ.add(cur.right);
}
}
return head;
}
private static Node genNode(String s) {
if(s.equals("null")) {
return null;
}
return new Node(Integer.valueOf(s));
}
}