Space Complexity - O ( n log n )

For every element to be processed, we keep looping down till we reach the leaf child node. And then elements are processed while coming up.

Thus to process element n, we recursively loop (or loop to stack the elements) upto height of that node O(h)

Since going down by height, we divide the scope into half (left or right subtree) - O(h) is log n

And each time we loop (through recursion or stack) - a new layer of stack is allocated in memory

Thus for all elements -

Time & Space Complexity = nO(h) = nlog n = n log n

Any tree traversal - Inorder, PreOrder, PostOrder, BFS, DFS - are all same O(n log n)

Given a binary tree, print out the nodes of the tree according to a

bottom-up "postorder" traversal -- both subtrees of a node are printed

out completely before the node itself is printed, and each left subtree

is printed before the right subtree.

package main.java.algo.datastructures.binarytree.traversal; import java.util.Stack; import main.java.algo.datastructures.binarytree.Node; /** ** So the tree... 4 / \ 2 5 / \ 1 3 / 0.5 ** Produces the output "1 3 2 5 4" ** ** http://codepad.org/QEVUNzYU **/ public class PostOrder { /** ************************** PostOrder : Recursive ************************** **/ //Produces the output "1 3 2 5 4". public void postOrderRecursive(Node node) { if (node == null) return; // first recur on both subtrees postOrderRecursive(node.left); postOrderRecursive(node.right); // then deal with the node System.out.print(node.data); } /** ************************** PostOrder : Iterative ************************** **/ /** 4 / \ 2 5 / \ 1 3 **/ // Why do we need a VISITED flag in POST ORDER?? // First remember that in post order, when we start reading from stack, we do peek first and not pop as in inorder and preorder. // Lets consider if there was NO visited flag - // // 1) After 1st postOrderPushLeftChildsToStack. Stack -> 4,2,1 // 2) Peek 1 - pushleftChilds(1.right) - since there was no child of 1, stack remained same. Stack -> 4,2,1 // 3) Pop 1, Process 1. Stack -> 4,2 // 4) Now Stack -> 4,2. Peek 2 - pushleftChilds(2.right) - added 3. Stack -> 4,2,3 // 5) Pop 3, Process 3. Stack again became -> 4,2 // // Now if we did not kept visited flag - it would again then go to step 4 and go into infinite loop of steps 4 and step 5. // By keeping visited flag, node 1 and node 3 is marked visited now. So, when after step 5, when it again goes to step 4, // there is no unvisted child of 2 that could be added to stack. To even after step 4, Stack -> 4,2 // Then 2 was popped and stack became Stack -> 4. // // Thus with visited flag, we avoid infinite loops as in DFS graph traversal. class BTNode { Object data; BTNode left; BTNode right; // post order is achieved with help of DFS, using a visited flag boolean visited; } public void postOrderIterative(BTNode n) { //using stack Stack<Object> s = new Stack<Object>(); // what doit(n.left) does postOrderPushLeftChildsToStack(s, n); // what happens when doit(n.right) is called while (!s.isEmpty()) { BTNode t = (BTNode) s.peek(); // Note it is peek, not pop. t = t.right; // what doit(n.left) does postOrderPushLeftChildsToStack(s, t); // processing on a node Node top = (Node) s.pop(); // Here current node to processed is the one on top of stack = s.pop() process(top); } } // it does what doit(n.left) was doing // pick only non visited items next time. Once visted, mark them as visited. public void postOrderPushLeftChildsToStack(Stack<Object> s, BTNode n) { while (n != null && n.visited == false) { n.visited = true; s.push(n); n = n.left; } } public void process(Node n) { System.out.println(n.data); } public void process(BTNode n) { System.out.println(n.data); } }

dịch vụ tạm ngừng, giải thể doanh nghiệp

ReplyDeletedịch vụ tạm ngừng, giải thể doanh nghiệp tại quận thanh xuân

dịch vụ tạm ngừng, giải thể doanh nghiệp tại quận hà đông

dịch vụ tạm ngừng, giải thể doanh nghiệp tại quận long biên

dịch vụ tạm ngừng, giải thể doanh nghiệp tại quận cầu giấy

dịch vụ tạm ngừng, giải thể doanh nghiệp tại bắc ninh

dịch vụ tạm ngừng, giải thể doanh nghiệp tại quận 3 tphcm

dịch vụ tạm ngừng, giải thể doanh nghiệp tại quận đống đa

dịch vụ tạm ngừng, giải thể doanh nghiệp tại quận thủ đức

dịch vụ tạm ngừng, giải thể doanh nghiệp tại huyện đông anh

dịch vụ tạm ngừng, giải thể doanh nghiệp tại huyện hoài đức

dịch vụ tạm ngừng, giải thể doanh nghiệp tại huyện nhà bè

dịch vụ tạm ngừng, giải thể doanh nghiệp tại bình dương

dịch vụ tạm ngừng, giải thể doanh nghiệp tại hưng yên