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)

package main.java.algo.datastructures.binarytree.traversal; import java.util.Stack; import main.java.algo.datastructures.binarytree.Node; public class DFSTreeTraversal { public void mirrorTreeWithOutRecursion(Node root) { Stack<Node> stack = new Stack<Node>(); stack.push(root); Node current = null; while (!stack.isEmpty()) { current = stack.pop(); // do the processing on a node process(current); if (current.left != null) stack.push(current.left); if (current.right != null) stack.push(current.right); } return; } // process // example - here we are processing to create mirror of a tree public void process(Node n) { Node temp = n.left; n.left = n.right; n.right = temp; } }

As per the definition of a DFS, shouldn't we push the right child of a node before the left child? So that when we pop, we first get the left child and we go through the entire left subtree before going to the right subtree?

ReplyDeleteIn your case, you are going over the right subtree before the left subtree.

This comment has been removed by the author.

DeleteHi, Great.. Tutorial is just awesome..It is really helpful for a newbie like me.. I am a regular follower of your blog. Really very informative post you shared here. Kindly keep blogging. If anyone wants to become a Front end developer learn from Javascript Training in Chennai . or learn thru JavaScript Online Training India. Nowadays JavaScript has tons of job opportunities on various vertical industry.

Deletedịch vụ thành lập chi nhánh văn phòng đại diện

ReplyDeletedịch vụ thành lập chi nhánh văn phòng đại diện tại thanh xuân

dịch vụ thành lập chi nhánh văn phòng đại diện tại hà đông

dịch vụ thành lập chi nhánh văn phòng đại diện tại long biên

dịch vụ thành lập chi nhánh văn phòng đại diện tại cầu giấy

dịch vụ thành lập chi nhánh văn phòng đại diện tại bắc ninh

dịch vụ thành lập chi nhánh văn phòng đại diện tại quận 3 tphcm

dịch vụ thành lập chi nhánh văn phòng đại diện tại đống đa

dịch vụ thành lập chi nhánh văn phòng đại diện tại quận thủ đức

dịch vụ thành lập chi nhánh văn phòng đại diện tại huyện đông anh

dịch vụ thành lập chi nhánh văn phòng đại diện tại huyện hoài đức

dịch vụ thành lập chi nhánh văn phòng đại diện tại huyện nhà bè

dịch vụ thành lập chi nhánh văn phòng đại diện tại bình dương

dịch vụ thành lập chi nhánh văn phòng đại diện tại hưng yên

either right first or left, IMHO - it will not effect time complexity O(~vertex) or space complexity O(~height)

ReplyDelete