Algorithm for iterating TreeView nodes in reverese from last leaf to root

Question

What is the best algorithm for iterating a TreeView WinForms control from last sheets to roots in reverse order? WITH#

Answer 1

The code below will visit each node and completely cross it, first in depth, until it reaches the leaf. Then, when it unwinds the stack, DoSomethingWithNode is called for each node. The depth parameter should show you that the nodes are returned in the reverse order.

 void ReverseTraverse(TreeNodeCollection nodes, int depth) { if (nodes == null) return; foreach (TreeNode child in nodes) { ReverseTraverse(child.Nodes, depth+1); DoSomethingWithNode(child, depth); } } 

To call it, assuming MyTreeView is an instance of TreeView :

 ReverseTraverse(MyTreeView.Nodes, 1); 

Note that this at first does not give you the deepest leaf nodes, but rather ensures that any leaf node is displayed before its parent node. If your tree looks like this:

 Node 1 Node 1.1 Node 1.2 Node 1.2.1 Node 2 Node 2.1 Node 2.1.1 Node 2.1.1.1 Node 2.1.2 

The output order will be:

 Node 1.1 Node 1.2.1 Node 1.2 Node 1 Node 2.1.1.1 Node 2.1.1 Node 2.1.2 Node 2.1 Node 2 

If you want to have the deepest nodes first (i.e. node 2.1.1.1 will be the first), then you will have to make a full round (in the direct order it will be easier) and build a list of nodes with their corresponding depths. Then sort the list by depth (descending) and display in order.

Answer 2

For a binary tree, you are looking for a reverse move in order. To do this, you can direct the nodes to the linked list (via the node connected to the right) while traversing the order. Then you read the linked list back to back.

• Convert the binary search tree to a doubly linked list using O (n) traversal.
• Move this doubly linked list back. You can use two pointers for this.

Then you can have fun and optimize it :)

Answer 3

If you have BT (Binary Tree), the best tree-like walk in a tree from leaves to root will be a pose-by-step. This visits the nodes in the following order: left -> right -> root. If you want to undo this, use: right -> left -> root.

pseudo code:

 BottomUpTraversal(x) BottomUpTraversal(x.left) BottomUpTraversal(x.right) print(x.key)