Tree traversal: Difference between revisions

Revision as of 18:01, 19 April 2022

Latest revision as of 19:29, 14 May 2025

(47 intermediate revisions by 28 users not shown)

Line 2:

{{Redirect-distinguish|Tree search|Search tree}}

{{refimprove|date=May 2009}}

{{graph search algorithm}}

In [[computer science]], '''tree traversal''' (also known as '''tree search''' and '''walking the tree''') is a form of [[graph traversal]] and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a [[Tree (data structure)|tree data structure]], exactly once. Such traversals are classified by the order in which the nodes are visited. The following algorithms are described for a [[binary tree]], but they may be generalized to other trees as well.

==Types==

{{Tree traversal demo}}

Unlike [[linked list]]s, [[one-dimensional [[Array data structure|arraysarray]]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]].

===Data structures for tree traversal===

Line 35:

:{{font color|red|F}}-{{font color|red|B}}-{{font color|red|A}}-{{font color|green|A}}-{{font color|#2A7FFF|A}}-{{font color|green|B}}-{{font color|red|D}}-{{font color|red|C}}-{{font color|green|C}}-{{font color|#2A7FFF|C}}-{{font color|green|D}}-{{font color|red|E}}-{{font color|green|E}}-{{font color|#2A7FFF|E}}-{{font color|#2A7FFF|D}}-{{font color|#2A7FFF|B}}-{{font color|green|F}}-{{font color|red|G}}-{{font color|green|G}}-{{font color|red|&thinsp;I}}-{{font color|red|H}}-{{font color|green|H}}-{{font color|#2A7FFF|H}}-{{font color|green|&thinsp;I}}-{{font color|#2A7FFF|&thinsp;I}}-{{font color|#2A7FFF|G}}-{{font color|#2A7FFF|F}}

===={{anchor|Preorder traversal|Pre-order traversal}}Pre-order, NLR====

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

# Recursively traverse the current node's left subtree.

Line 42:

The pre-order traversal is a [[Topological sorting|topologically sorted]] one, because a parent node is processed before any of its child nodes is done.

===={{anchor|Postorder traversal|Post-order traversal}}Post-order, LRN====

# Recursively traverse the current node's left subtree.

# Recursively traverse the current node's right subtree.

# 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====

# Recursively traverse the current node's left subtree.

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

Line 56:

In a [[binary search tree]] ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, in-order traversal retrieves the keys in ''ascending'' sorted order.<ref>{{cite web |url=https://www.math.ucla.edu/~wittman/10b.1.10w/Lectures/Lec18.pdf |website=[[UCLA]] Math |last=Wittman |first=Todd |access-date=January 2, 2016 |title=Tree Traversal |url-status=dead |archive-url=https://web.archive.org/web/20150213195803/http://www.math.ucla.edu/~wittman/10b.1.10w/Lectures/Lec18.pdf |archive-date=February 13, 2015 }} </ref>

===={{anchor|Reverse preorder traversal|Reverse pre-order traversal}}Reverse pre-order, NRL====

# Visit the current node.

# Recursively traverse the current node's right subtree.

# Recursively traverse the current node's left subtree.

===={{anchor|Reverse postorder traversal|Reverse post-order traversal}}Reverse post-order, RLN====

# Recursively traverse the current node's right subtree.

# Recursively traverse the current node's left subtree.

# Visit the current node.

===={{anchor|Reverse inorder traversal|Reverse in-order traversal}}Reverse in-order, RNL====

# Recursively traverse the current node's right subtree.

# Visit the current node.

Line 95:

==Applications==

[[File:AST binary tree arith variables.svg|260px|thumb|Tree representing the arithmetic expression: ''A'' * {{nowrap|(''B'' − ''C'')}} + {{nowrap|(''D'' + ''E'')}}]]

Pre-order traversal can be used to make a prefix expression ([[Polish notation]]) from [[Parse tree|expression trees]]: traverse the expression tree pre-orderly. For example, traversing the depicted arithmetic expression in pre-order yields "+ * ''A'' − ''B'' ''C'' + ''D'' ''E''". In prefix notation, there is no need for any parentheses as long as each operator has a fixed number of operands. PreorderPre-order traversal is also used to create a copy of the tree.

Post-order traversal can generate a postfix representation ([[Reverse Polish notation]]) of a binary tree. Traversing the depicted arithmetic expression in post-order yields "''A'' ''B'' ''C'' − * ''D'' ''E'' + +"; the latter can easily be transformed into [[machine code]] to evaluate the expression by a [[stack machine]]. PostorderPost-order traversal is also used to delete the tree. Each node is freed after freeing its children.

In-order traversal is very commonly used on [[binary search tree]]s because it returns values from the underlying set in order, according to the comparator that set up the binary search tree.

Line 103:

==Implementations==

{{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).

====Pre-order====

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.

Several alternative implementations are also mentioned.

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

{|

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

Line 130 ⟶ 136:

|}

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

====Post-order====

{|

|- style="vertical-align:top"

Line 143 ⟶ 148:

|

'''procedure''' iterativePostorder(node)

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

'''return'''

stack ← '''empty stack'''

lastNodeVisited ← '''null'''

Line 160 ⟶ 167:

|}

===={{anchor|Inorder traversal code|In-order traversal code}}In-order implementation====

====In-order====

{{anchor|Inorder traversal|In-order traversal}}

{|

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

Line 173 ⟶ 180:

|

'''procedure''' iterativeInorder(node)

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

'''return'''

stack ← '''empty stack'''

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

Line 184 ⟶ 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 300 ⟶ 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 324 ⟶ 333:

* [https://web.archive.org/web/20110606032941/http://dev.mysql.com/tech-resources/articles/hierarchical-data.html Managing Hierarchical Data in MySQL]

* [http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html Working with Graphs in MySQL]

* [https://favtutor.com/blogs/tree-traversal-python-with-recursion Sample code for recursive tree traversal in Python.]

* [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}}

{{DEFAULTSORT:Tree Traversal}}