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

Time Complexity - O ( n log n )

Space Complexity - O ( n log n )

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.LinkedList; import java.util.Queue; import main.java.algo.datastructures.binarytree.Node; public class BFSTreeTraversal { public void mirrorTreeWithOutRecursion(Node root) { Queue<Node> queue = new LinkedList<Node>(); queue.add(root); Node current = null; while (!queue.isEmpty()) { current = queue.poll(); // do the processing on a node process(current); if (current.left != null) queue.add(current.left); if (current.right != null) queue.add(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; } }

dịch vụ thành lập doanh nghiệp công ty trọn gói

ReplyDeletedịch vụ thành lập doanh nghiệp công ty tại thanh xuân

dịch vụ thành lập doanh nghiệp công ty tại hà đông

dịch vụ thành lập doanh nghiệp công ty tại long biên

dịch vụ thành lập doanh nghiệp công ty tại cầu giấy

dịch vụ thành lập doanh nghiệp công ty tại bắc ninh

dịch vụ thành lập doanh nghiệp công ty tại quận 3 tphcm

dịch vụ thành lập doanh nghiệp công ty tại quận đống đa

dịch vụ thành lập doanh nghiệp công ty tại quận thủ đức

dịch vụ thành lập doanh nghiệp công ty tại huyện đông anh

dịch vụ thành lập doanh nghiệp công ty tại huyện nhà bè

dịch vụ thành lập doanh nghiệp công ty tại huyện hoài đức

dịch vụ thành lập doanh nghiệp công ty tại bình dương

dịch vụ thành lập doanh nghiệp công ty tại hưng yên

Hi, 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 JQuery Training . or learn thru ES6 Online Training India. Nowadays JavaScript has tons of job opportunities on various vertical industry.

ReplyDeleteAttend The Analytics Course in Bangalore From ExcelR. Practical Analytics Course in Bangalore Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Analytics Course in Bangalore.

ReplyDeleteExcelR Analytics Course in Bangalore

Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!

ReplyDeletedata analytics courses