Tree traversal: Difference between revisions

Revision as of 10:44, 23 August 2023

Latest revision as of 19:29, 14 May 2025

(17 intermediate revisions by 13 users not shown)

Line 6:

==Types==

{{Tree traversal demo}}

Unlike [[linked list]]s, [[one-dimensional array]]s and other [[List of data structures#Linear data structures|linear data structures]], which are canonically traversed in linear order, trees may be traversed in multiple ways. They may be traversed in [[Depth-first search|depth-first]] or [[Breadth-first search|breadth-first]] order. There are three common ways to traverse them in depth-first order: in-order, pre-order and post-order.<ref name="holtenotes">{{cite web|url=http://webdocs.cs.ualberta.ca/~holte/T26/tree-traversal.html|title=Lecture 8, Tree Traversal|access-date=2 May 2015}}</ref> Beyond these basic traversals, various more complex or hybrid schemes are possible, such as [[depth-limited search]]es like [[iterative deepening depth-first search]]. The latter, as well as breadth-first search, can also be used to traverse infinite trees, see [[#Infinite trees|below]].

Line 46 ⟶ 47:

# Visit the current node (in the figure: position blue).

Post-order traversal can be useful to get [[Reverse_Polish_notation|postfix expression]] of a [[binary expression tree]].

===={{anchor|Inorder traversal|In-order traversal}}In-order, LNR====

Line 103 ⟶ 104:

{{unreferenced section|date=June 2013}}

===Depth-first search implementation===

Below are examples of [[stack (abstract data type)|stack]]-based implementation for pre-order, post-order and in-order traversal in recursive approach (left) as well as iterative approach (right).

Implementations in iterative approach are able to avoid the [[Recursion (computer science)#Recursion versus iteration|drawbacks of recursion]], particularly limitations of stack space and performance issues.

// import visualization libraries {

const { Tracer, Array1DTracer, GraphTracer, LogTracer, Layout, VerticalLayout } = require('algorithm-visualizer');

// }

Several alternative implementations are also mentioned.

const G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],

];

===={{anchor|Pre-order traversal code|Pre-order traversal code}}Pre-order implementation====

const T = [ // mapping to G as a binary tree , [i][0] indicates left child, [i][1] indicates right child

{|

[-1, -1],

|- style="vertical-align:top;"

[0, 2],

|

[-1, -1],

'''procedure''' preorder(node)

[1, 4],

'''if''' node = '''null'''

[-1, -1],

'''return'''

[3, 8],

visit(node)

[-1, 7],

preorder(node.left)

[-1, -1],

preorder(node.right)

[6, 10],

|

[-1, -1],

'''procedure''' iterativePreorder(node)

[9, -1],

'''if''' node = '''null'''

];

'''return'''

stack ← '''empty stack'''

// define tracer variables {

stack.push(node)

const treeTracer = new GraphTracer('Traversal In-order');

'''while''' '''not''' stack.isEmpty()

const arrayTracer = new Array1DTracer('Print In-order');

node ← stack.pop()

const logger = new LogTracer('Log');

visit(node)

Layout.setRoot(new VerticalLayout([treeTracer, arrayTracer, logger]));

// right child is pushed first so that left is processed first

treeTracer.set(G);

'''if''' node.right ≠ '''null'''

treeTracer.layoutTree(5);

stack.push(node.right)

arrayTracer.set(new Array(T.length).fill('-'));

'''if''' node.left ≠ '''null'''

Tracer.delay();

stack.push(node.left)

// }

|}

let index = 0;

function inOrder(root, parent) {

if (root === -1) {

// logger {

logger.println('No more nodes. Backtracking.');

Tracer.delay();

// }

return;

}

// visualize {

logger.println(`Reached ${root}`);

treeTracer.visit(root, parent);

Tracer.delay();

logger.println(` Going left from ${root}`);

Tracer.delay();

// }

inOrder(T[root][0], root);

// visualize {

logger.println(`Printing ${root}`);

treeTracer.leave(root);

arrayTracer.patch(index++, root);

Tracer.delay();

logger.println(` Going right from ${root}`);

Tracer.delay();

// }

inOrder(T[root][1], root);

}

inOrder(5); // node with key 5 is the root

// logger {

logger.println('Finished');

// }

===={{anchor|Post-order traversal code|Post-order traversal code}}Post-order implementation====

Line 197 ⟶ 148:

|

'''procedure''' iterativePostorder(node)

'''if''' node = '''null'''

'''return'''

stack ← '''empty stack'''

lastNodeVisited ← '''null'''

Line 227 ⟶ 180:

|

'''procedure''' iterativeInorder(node)

'''if''' node = '''null'''

'''return'''

stack ← '''empty stack'''

'''while''' '''not''' stack.isEmpty() '''or''' node ≠ '''null'''

Line 238 ⟶ 193:

|}

====Another variant of Prepre-order====

If the tree is represented by an array (first index is 0), it is possible to calculate the index of the next element:<ref>{{Cite web|title=constexpr tree structures|url=https://fekir.info/post/constexpr-tree/#_dfs_traversal|access-date=2021-08-15|website=Fekir's Blog|date=9 August 2021|language=en}}</ref>{{clarify|reason=Explicitly mention the restrictions on trees in order to be handled by this algorithm. Since there is no isLeaf() test, it seems that all leaves must be on maximal depth or one level above it, like in a [[heap (data structure)]].|date=November 2021}}

Line 354 ⟶ 309:

Thus, simple depth-first or breadth-first searches do not traverse every infinite tree, and are not efficient on very large trees. However, hybrid methods can traverse any (countably) infinite tree, essentially via a [[Diagonal argument (disambiguation)|diagonal argument]] ("diagonal"—a combination of vertical and horizontal—corresponds to a combination of depth and breadth).

Concretely, given the infinitely branching tree of infinite depth, label the root (), the children of the root (1), (2), …..., the grandchildren (1, 1), (1, 2), …..., (2, 1), (2, 2), …..., and so on. The nodes are thus in a [[bijection|one-to-one]] correspondence with finite (possibly empty) sequences of positive numbers, which are countable and can be placed in order first by sum of entries, and then by [[lexicographic order]] within a given sum (only finitely many sequences sum to a given value, so all entries are reached—formally there are a finite number of [[Composition (number theory)|compositions]] of a given natural number, specifically 2^''n''−1 compositions of {{nowrap|1=''n'' ≥ 1}}), which gives a traversal. Explicitly:

# ()

Line 380 ⟶ 335:

* [http://rosettacode.org/wiki/Tree_traversal See tree traversal implemented in various programming language] on [[Rosetta Code]]

* [http://www.perlmonks.org/?node_id=600456 Tree traversal without recursion]

* [https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/ Tree Traversal Algorithms]

* [https://faculty.cs.niu.edu/~mcmahon/CS241/Notes/Data_Structures/binary_tree_traversals.html Binary Tree Traversal]

* [https://www.simplilearn.com/tutorials/data-structure-tutorial/tree-traversal-in-data-structure Tree Traversal In Data Structure]

{{Graph traversal algorithms}}