637:
690:
255:
803:
43:
1721:
child, etc. Thus at each step one can either go down (append a (, 1) to the end) or go right (add one to the last number) (except the root, which is extra and can only go down), which shows the correspondence between the infinite binary tree and the above numbering; the sum of the entries (minus one) corresponds to the distance from the root, which agrees with the 2 nodes at depth
331:
The trace of a traversal is called a sequentialisation of the tree. The traversal trace is a list of each visited node. No one sequentialisation according to pre-, in- or post-order describes the underlying tree uniquely. Given a tree with distinct elements, either pre-order or post-order paired with
216:
Traversing a tree involves iterating over all nodes in some manner. Because from a given node there is more than one possible next node (it is not a linear data structure), then, assuming sequential computation (not parallel), some nodes must be deferred—stored in some way for later visiting. This is
1645:
A basic requirement for traversal is to visit every node eventually. For infinite trees, simple algorithms often fail this. For example, given a binary tree of infinite depth, a depth-first search will go down one side (by convention the left side) of the tree, never visiting the rest, and indeed an
1720:
This can be interpreted as mapping the infinite depth binary tree onto this tree and then applying breadth-first search: replace the "down" edges connecting a parent node to its second and later children with "right" edges from the first child to the second child, from the second child to the third
1654:
On the other hand, given a tree of depth 2, where the root has infinitely many children, and each of these children has two children, a depth-first search will visit all nodes, as once it exhausts the grandchildren (children of children of one node), it will move on to the next (assuming it is not
335:
There are three methods at which position of the traversal relative to the node (in the figure: red, green, or blue) the visit of the node shall take place. The choice of exactly one color determines exactly one visit of a node as described below. Visit at all three colors results in a threefold
627:
Depending on the problem at hand, pre-order, post-order, and especially one of the number of subtrees − 1 in-order operations may be optional. Also, in practice more than one of pre-order, post-order, and in-order operations may be required. For example, when inserting into a ternary tree, a
1499:
A binary tree is threaded by making every left child pointer (that would otherwise be null) point to the in-order predecessor of the node (if it exists) and every right child pointer (that would otherwise be null) point to the in-order successor of the node (if it exists).
1551:
based level-order traversal, and will require space proportional to the maximum number of nodes at a given depth. This can be as much as half the total number of nodes. A more space-efficient approach for this type of traversal can be implemented using an
1480:
for the recursive and a parent (ancestor) stack for the iterative ones. In a poorly balanced tree, this can be considerable. With the iterative implementations we can remove the stack requirement by maintaining parent pointers in each node, or by
1650:
nodes, as it has not reached a leaf (and in fact never will). By contrast, a breadth-first (level-order) traversal will traverse a binary tree of infinite depth without problem, and indeed will traverse any tree with bounded branching factor.
1677:
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
1630:), as infinite data structures can often be easily defined and worked with, though they are not (strictly) evaluated, as this would take infinite time. Some finite trees are too large to represent explicitly, such as the
1669:
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
195:
order. There are three common ways to traverse them in depth-first order: in-order, pre-order and post-order. Beyond these basic traversals, various more complex or hybrid schemes are possible, such as
1328:
Note that the function does not use keys, which means that the sequential structure is completely recorded by the binary search tree’s edges. For traversals without change of direction, the (
240:
Depth-first search is easily implemented via a stack, including recursively (via the call stack), while breadth-first search is easily implemented via a queue, including corecursively.
750:". In prefix notation, there is no need for any parentheses as long as each operator has a fixed number of operands. Pre-order traversal is also used to create a copy of the tree.
579:
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, reverse in-order traversal retrieves the keys in
1366:
2038:
1451:
520:
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
1655:
post-order, in which case it never reaches the root). By contrast, a breadth-first search will never reach the grandchildren, as it seeks to exhaust the children first.
1395:
1418:
1471:
1682:
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
2031:
1977:
2139:
1553:
201:
921:
stack.isEmpty() node ← stack.pop() visit(node) // right child is pushed first so that left is processed first
1019:
peekNode ← stack.peek() // if right child exists and traversing node // from left child, then move right
1857:
163:, exactly once. Such traversals are classified by the order in which the nodes are visited. The following algorithms are described for a
2024:
1686:
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
2117:
1821:
If the traversal is taken the other way around (clockwise) then the traversal is called reversed. This is described in particular for
1671:
332:
in-order is sufficient to describe the tree uniquely. However, pre-order with post-order leaves some ambiguity in the tree structure.
669:
There are also tree traversal algorithms that classify as neither depth-first search nor breadth-first search. One such algorithm is
2287:
850:
126:
1321:
oldnode ≠ node.child // now oldnode = node.child, // i.e. node = ancestor (and predecessor/successor) of original node
591:
To traverse arbitrary trees (not necessarily binary trees) with depth-first search, perform the following operations at each node:
2272:
2011:
732:: traverse the expression tree pre-orderly. For example, traversing the depicted arithmetic expression in pre-order yields "+ *
824:
60:
2006:
2204:
1923:
1797:
828:
628:
pre-order operation is performed by comparing items. A post-order operation may be needed afterwards to re-balance the tree.
107:
64:
789:
because it returns values from the underlying set in order, according to the comparator that set up the binary search tree.
1836:"Algorithms, Which combinations of pre-, post- and in-order sequentialisation are unique?, Computer Science Stack Exchange"
79:
2122:
2194:
1953:
Dale, Nell. Lilly, Susan D. "Pascal Plus Data
Structures". D. C. Heath and Company. Lexington, MA. 1995. Fourth Edition.
1687:
1124:
If the tree is represented by an array (first index is 0), it is possible to calculate the index of the next element:
86:
2184:
813:
187:, which are canonically traversed in linear order, trees may be traversed in multiple ways. They may be traversed in
1524:
It is more prone to errors when both the children are not present and both values of nodes point to their ancestors.
222:
218:
832:
817:
636:
53:
2277:
605:
from 1 to the current node's number of subtrees − 1, or from the latter to the former for reverse traversal, do:
2227:
2001:
93:
2242:
1959:
2189:
2161:
1956:
Drozdek, Adam. "Data
Structures and Algorithms in C++". Brook/Cole. Pacific Grove, CA. 2001. Second edition.
1592:
If the tree is represented by an array (first index is 0), it is sufficient iterating through all elements:
1266:, so that the binary search tree may be sequentially in-order-traversed and searched in the given direction
754:
670:
490:
184:
2068:
1618:
While traversal is usually done for trees with a finite number of nodes (and hence finite depth and finite
75:
2232:
2199:
2080:
1623:
1548:
494:
225:(FIFO). As a tree is a self-referential (recursively defined) data structure, traversal can be defined by
1674:("diagonal"—a combination of vertical and horizontal—corresponds to a combination of depth and breadth).
2219:
2176:
1335:
180:
160:
1423:
782:. Post-order traversal is also used to delete the tree. Each node is freed after freeing its children.
2112:
2107:
2085:
1494:
648:
197:
192:
1982:
1476:
All the above implementations require stack space proportional to the height of the tree which is a
2237:
2073:
1683:
689:
467:
1871:
2282:
2253:
2134:
1329:
786:
678:
576:
517:
309:
To traverse binary trees with depth-first search, perform the following operations at each node:
249:
233:, in a natural and clear fashion; in these cases the deferred nodes are stored implicitly in the
188:
2209:
1158:
leaf ← i - size/2 parent ← bubble_up(array, i, leaf) i ← parent * 2 + 2
204:. The latter, as well as breadth-first search, can also be used to traverse infinite trees, see
1745:
2156:
2097:
159:
and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a
1819:
The execution of N before, between, or after L and R determines one of the described methods.
1932:
1619:
254:
140:
100:
1783:
1178:
function, which is shown here in an implementation without parent pointers, i.e. it uses a
2060:
2047:
1627:
1371:
725:
156:
1896:
306:(DFS), the search tree is deepened as much as possible before going to the next sibling.
1400:
757:) of a binary tree. Traversing the depicted arithmetic expression in post-order yields "
673:, which concentrates on analyzing the most promising moves, basing the expansion of the
1971:
1663:
1659:
1456:
2016:
2266:
2151:
1936:
1287:
node ← newnode stack.push(node) newnode ← node.child
779:
1991:
1030:
lastNodeVisited ≠ peekNode.right node ← peekNode.right
775:
661:, the search tree is broadened as much as possible before going to the next depth.
17:
1528:
Morris traversal is an implementation of in-order traversal that uses threading:
2102:
1188:
search(bst, key) // returns a (node, stack) node ← bst.root stack ←
802:
674:
230:
176:
164:
42:
31:
1317:) oldnode ← node node ← stack.pop() // parent of oldnode
470:
one, because a parent node is processed before any of its child nodes is done.
1477:
729:
234:
1817:
L before R means the (standard) counter-clockwise traversal—as in the figure.
1679:
1662:; for example, the breadth-first search of the depth 2 tree above will take
1639:
1631:
1622:) it can also be done for infinite trees. This is of particular interest in
226:
1996:
1573:
queue.isEmpty() node ← queue.dequeue() visit(node)
1666:·2 steps: ω for the first level, and then another ω for the second level.
1134:(leaf + 1) % (k * 2) ≠ k i ← (i - 1)/2 k ← 2 * k
1112:
node ← stack.pop() visit(node) node ← node.right
1987:
1921:
Morris, Joseph M. (1979). "Traversing binary trees simply and cheaply".
1658:
A more sophisticated analysis of running time can be given via infinite
1507:
Avoids recursion, which uses a call stack and consumes memory and time.
1835:
1420:
1 step for edge up and 1 for edge down. The worst-case complexity is
1713:(1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)
336:
visit of the same node yielding the “all-order” sequentialisation:
1635:
635:
1170:
to be started with may have been found in the binary search tree
2166:
2090:
1865:
1642:, and so it is useful to analyze them as if they were infinite.
2020:
967:
postorder(node.left) postorder(node.right) visit(node)
1988:
See tree traversal implemented in various programming language
1482:
1034:
visit(peekNode) lastNodeVisited ← stack.pop()
891:
visit(node) preorder(node.left) preorder(node.right)
796:
36:
724:
Pre-order traversal can be used to make a prefix expression (
1429:
1341:
753:
Post-order traversal can generate a postfix representation (
2146:
2129:
1276:
inorderNext(node, dir, stack) newnode ← node.child
1211:key < node.key node ← node.left
1064:
inorder(node.left) visit(node) inorder(node.right)
316:
Execute the following three operations in a certain order:
1690:
of a given natural number, specifically 2 compositions of
1771:
1298:(node, stack) // node does not have a dir-child:
1130:
bubbleUp(array, i, leaf) k ← 1 i ← (i - 1)/2
325:
R: Recursively traverse the current node's right subtree.
1825:, when the data are to be retrieved in descending order.
322:
L: Recursively traverse the current node's left subtree.
1728:
in the infinite binary tree (2 corresponds to binary).
509:
Visit the current node (in the figure: position green).
1108:stack.push(node) node ← node.left
1015:stack.push(node) node ← node.left
565:
Recursively traverse the current node's right subtree.
549:
Recursively traverse the current node's right subtree.
536:
Recursively traverse the current node's right subtree.
512:
Recursively traverse the current node's right subtree.
485:
Visit the current node (in the figure: position blue).
482:
Recursively traverse the current node's right subtree.
462:
Recursively traverse the current node's right subtree.
167:, but they may be generalized to other trees as well.
30:"Tree search" redirects here. Not to be confused with
1459:
1426:
1403:
1374:
1338:
620:
Recursively traverse the current node's last subtree.
571:
Recursively traverse the current node's left subtree.
552:
Recursively traverse the current node's left subtree.
539:
Recursively traverse the current node's left subtree.
506:
Recursively traverse the current node's left subtree.
479:
Recursively traverse the current node's left subtree.
459:
Recursively traverse the current node's left subtree.
456:
Visit the current node (in the figure: position red).
258:
Depth-first traversal (dotted path) of a binary tree:
2218:
2175:
2059:
67:. Unsourced material may be challenged and removed.
1646:in-order or post-order traversal will never visit
1465:
1445:
1412:
1389:
1360:
1154:i < size/2 i ← i * 2 + 1
774:+ +"; the latter can easily be transformed into
623:Visit the current node for post-order traversal.
598:Visit the current node for pre-order traversal.
1547:Also, listed below is pseudocode for a simple
615:Visit the current node for in-order traversal.
2032:
693:Tree representing the arithmetic expression:
8:
1538:Revert the changes to restore original tree.
1146:i ≠ array.size visit(array)
785:In-order traversal is very commonly used on
831:. Unsourced material may be challenged and
2039:
2025:
2017:
1960:"Tree Transversal" (math.northwestern.edu)
1150:i = size - 1 i ← size
489:Post-order traversal can be useful to get
287:Post-order (node visited at position blue
1521:We can make only one traversal at a time.
1489:Morris in-order traversal using threading
1458:
1428:
1427:
1425:
1402:
1373:
1340:
1339:
1337:
851:Learn how and when to remove this message
595:If the current node is empty then return.
313:If the current node is empty then return.
275:In-order (node visited at position green
127:Learn how and when to remove this message
1697:), which gives a traversal. Explicitly:
688:
608:Recursively traverse the current node's
295: A, C, E, D, B, H, I, G, F.
283: A, B, C, D, E, F, G, H, I;
271: F, B, A, D, C, E, G, I, H;
263:Pre-order (node visited at position red
253:
1972:Storing Hierarchical Data in a Database
1764:
1762:
1737:
1532:Create links to the in-order successor.
1554:iterative deepening depth-first search
1510:The node keeps a record of its parent.
1162:Advancing to the next or previous node
202:iterative deepening depth-first search
1822:
7:
829:adding citations to reliable sources
65:adding citations to reliable sources
1978:Managing Hierarchical Data in MySQL
1182:for holding the ancestor pointers.
205:
1361:{\displaystyle {\mathcal {O}}(1),}
212:Data structures for tree traversal
25:
1581:queue.enqueue(node.left)
1535:Print the data using these links.
1446:{\displaystyle {\mathcal {O}}(h)}
864:Depth-first search implementation
2012:Tree Traversal In Data Structure
1997:Tree traversal without recursion
1773:. Free Software Foundation, Inc.
1610:array.size visit(array)
1234:returns an in-order-neighbor of
801:
778:to evaluate the expression by a
41:
2254:List of graph search algorithms
1368:because a full traversal takes
929:stack.push(node.right)
288:
276:
264:
52:needs additional citations for
1974:with traversal examples in PHP
1924:Information Processing Letters
1798:"Preorder Traversal Algorithm"
1440:
1434:
1352:
1346:
1142:preorder(array) i ← 0
1:
1785:Binary Tree Traversal Methods
1562:levelorder(node) queue ←
975:iterativePostorder(node)
466:The pre-order traversal is a
1983:Working with Graphs in MySQL
1937:10.1016/0020-0190(79)90068-1
1305:stack.isEmpty()
1120:Another variant of Pre-order
899:iterativePreorder(node)
643:: F, B, G, A, D, I, C, E, H.
1897:"constexpr tree structures"
1746:"Lecture 8, Tree Traversal"
1710:(1, 1, 1) (1, 2) (2, 1) (3)
1473:as the height of the tree.
1203:key = node.key
1072:iterativeInorder(node)
2304:
1589:queue.enqueue(node.right)
1492:
646:
319:N: Visit the current node.
247:
29:
2251:
2002:Tree Traversal Algorithms
1518:The tree is more complex.
1199:stack.push(node)
945:Post-order implementation
2288:Iteration in programming
1566:queue.enqueue(node)
1397:steps for a BST of size
1332:) average complexity is
869:Pre-order implementation
2273:Trees (data structures)
2162:Monte Carlo tree search
1174:by means of a standard
1042:In-order implementation
755:Reverse Polish notation
671:Monte Carlo tree search
568:Visit the current node.
555:Visit the current node.
544:Reverse post-order, RLN
533:Visit the current node.
1624:functional programming
1598:levelorder(array)
1467:
1447:
1414:
1391:
1362:
1215:node ← node.right
1207:(node, stack)
937:stack.push(node.left)
721:
644:
528:Reverse pre-order, NRL
495:binary expression tree
299:
198:depth-limited searches
185:linear data structures
181:one-dimensional arrays
2220:Minimum spanning tree
2007:Binary Tree Traversal
1468:
1448:
1415:
1392:
1363:
914:stack.push(node)
692:
681:of the search space.
639:
560:Reverse in-order, RNL
257:
2205:Shortest path faster
2113:Breadth-first search
2108:Bidirectional search
2054:traversal algorithms
1877:on February 13, 2015
1543:Breadth-first search
1495:Threaded binary tree
1457:
1424:
1401:
1390:{\displaystyle 2n-2}
1372:
1336:
956:postorder(node)
825:improve this section
655:breadth-first search
649:Breadth-first search
632:Breadth-first search
468:topologically sorted
61:improve this article
2140:Iterative deepening
1769:Pfaff, Ben (2004).
1684:lexicographic order
1626:(particularly with
1262:), and the updated
880:preorder(node)
787:binary search trees
161:tree data structure
27:Class of algorithms
18:Pre-order traversal
2135:Depth-first search
1483:threading the tree
1463:
1443:
1413:{\displaystyle n,}
1410:
1387:
1358:
1053:inorder(node)
990:lastNodeVisited ←
722:
659:level-order search
645:
577:binary search tree
518:binary search tree
491:postfix expression
304:depth-first search
300:
250:Depth-first search
244:Depth-first search
2260:
2259:
2157:Jump point search
2098:Best-first search
1672:diagonal argument
1466:{\displaystyle h}
1117:
1116:
1039:
1038:
1023:peekNode.right ≠
942:
941:
861:
860:
853:
229:or, more subtly,
217:often done via a
137:
136:
129:
111:
16:(Redirected from
2295:
2278:Graph algorithms
2041:
2034:
2027:
2018:
1941:
1940:
1918:
1912:
1911:
1909:
1908:
1893:
1887:
1886:
1884:
1882:
1876:
1870:. Archived from
1862:
1858:"Tree Traversal"
1853:
1847:
1846:
1844:
1842:
1832:
1826:
1823:reverse in-order
1815:
1809:
1808:
1806:
1804:
1794:
1788:
1781:
1775:
1774:
1766:
1757:
1756:
1754:
1752:
1742:
1727:
1696:
1620:branching factor
1485:(next section).
1472:
1470:
1469:
1464:
1452:
1450:
1449:
1444:
1433:
1432:
1419:
1417:
1416:
1411:
1396:
1394:
1393:
1388:
1367:
1365:
1364:
1359:
1345:
1344:
1269:
1265:
1261:
1257:
1249:
1245:
1237:
1181:
1173:
1169:
1093:stack.isEmpty()
1046:
1045:
1000:stack.isEmpty()
949:
948:
873:
872:
856:
849:
845:
842:
836:
805:
797:
730:expression trees
720:
708:
446:
442:
438:
434:
430:
426:
422:
418:
414:
410:
406:
402:
398:
394:
390:
386:
382:
378:
374:
370:
366:
362:
358:
354:
350:
346:
342:
290:
278:
266:
153:walking the tree
141:computer science
132:
125:
121:
118:
112:
110:
76:"Tree traversal"
69:
45:
37:
21:
2303:
2302:
2298:
2297:
2296:
2294:
2293:
2292:
2263:
2262:
2261:
2256:
2247:
2214:
2171:
2055:
2045:
1968:
1950:
1945:
1944:
1920:
1919:
1915:
1906:
1904:
1903:. 9 August 2021
1895:
1894:
1890:
1880:
1878:
1874:
1860:
1856:Wittman, Todd.
1855:
1854:
1850:
1840:
1838:
1834:
1833:
1829:
1820:
1818:
1816:
1812:
1802:
1800:
1796:
1795:
1791:
1782:
1778:
1768:
1767:
1760:
1750:
1748:
1744:
1743:
1739:
1734:
1722:
1691:
1660:ordinal numbers
1628:lazy evaluation
1616:
1611:
1590:
1545:
1514:Disadvantages:
1497:
1491:
1455:
1454:
1422:
1421:
1399:
1398:
1370:
1369:
1334:
1333:
1326:
1267:
1263:
1259:
1251:
1247:
1239:
1235:
1228:
1179:
1171:
1167:
1164:
1159:
1122:
1113:
1065:
1044:
1035:
968:
947:
938:
892:
871:
866:
857:
846:
840:
837:
822:
806:
795:
793:Implementations
726:Polish notation
710:
698:
687:
679:random sampling
667:
651:
634:
589:
587:Arbitrary trees
562:
546:
530:
503:
476:
474:Post-order, LRN
453:
444:
440:
436:
432:
428:
424:
420:
416:
412:
408:
404:
400:
396:
392:
388:
384:
380:
376:
372:
368:
364:
360:
356:
352:
348:
344:
340:
298:
294:
282:
270:
252:
246:
214:
173:
157:graph traversal
155:) is a form of
147:(also known as
133:
122:
116:
113:
70:
68:
58:
46:
35:
28:
23:
22:
15:
12:
11:
5:
2301:
2299:
2291:
2290:
2285:
2280:
2275:
2265:
2264:
2258:
2257:
2252:
2249:
2248:
2246:
2245:
2243:Reverse-delete
2240:
2235:
2230:
2224:
2222:
2216:
2215:
2213:
2212:
2207:
2202:
2197:
2195:Floyd–Warshall
2192:
2187:
2181:
2179:
2173:
2172:
2170:
2169:
2164:
2159:
2154:
2149:
2144:
2143:
2142:
2132:
2127:
2126:
2125:
2120:
2110:
2105:
2100:
2095:
2094:
2093:
2088:
2083:
2071:
2065:
2063:
2057:
2056:
2046:
2044:
2043:
2036:
2029:
2021:
2015:
2014:
2009:
2004:
1999:
1994:
1985:
1980:
1975:
1967:
1966:External links
1964:
1963:
1962:
1957:
1954:
1949:
1946:
1943:
1942:
1931:(5): 197–200.
1913:
1888:
1848:
1827:
1810:
1789:
1776:
1758:
1736:
1735:
1733:
1730:
1715:
1714:
1711:
1708:
1705:
1702:
1615:
1614:Infinite trees
1612:
1594:
1558:
1544:
1541:
1540:
1539:
1536:
1533:
1526:
1525:
1522:
1519:
1512:
1511:
1508:
1493:Main article:
1490:
1487:
1462:
1442:
1439:
1436:
1431:
1409:
1406:
1386:
1383:
1380:
1377:
1357:
1354:
1351:
1348:
1343:
1325:(node, stack)
1272:
1184:
1163:
1160:
1126:
1121:
1118:
1115:
1114:
1068:
1066:
1049:
1043:
1040:
1037:
1036:
971:
969:
952:
946:
943:
940:
939:
895:
893:
876:
870:
867:
865:
862:
859:
858:
809:
807:
800:
794:
791:
686:
683:
666:
663:
647:Main article:
633:
630:
625:
624:
621:
618:
617:
616:
613:
599:
596:
588:
585:
583:sorted order.
573:
572:
569:
566:
561:
558:
557:
556:
553:
550:
545:
542:
541:
540:
537:
534:
529:
526:
524:sorted order.
514:
513:
510:
507:
502:
499:
487:
486:
483:
480:
475:
472:
464:
463:
460:
457:
452:
451:Pre-order, NLR
449:
448:
447:
329:
328:
327:
326:
323:
320:
314:
297:
296:
284:
272:
259:
248:Main article:
245:
242:
213:
210:
172:
169:
145:tree traversal
135:
134:
49:
47:
40:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
2300:
2289:
2286:
2284:
2281:
2279:
2276:
2274:
2271:
2270:
2268:
2255:
2250:
2244:
2241:
2239:
2236:
2234:
2231:
2229:
2226:
2225:
2223:
2221:
2217:
2211:
2208:
2206:
2203:
2201:
2198:
2196:
2193:
2191:
2188:
2186:
2183:
2182:
2180:
2178:
2177:Shortest path
2174:
2168:
2165:
2163:
2160:
2158:
2155:
2153:
2152:Fringe search
2150:
2148:
2145:
2141:
2138:
2137:
2136:
2133:
2131:
2128:
2124:
2121:
2119:
2118:Lexicographic
2116:
2115:
2114:
2111:
2109:
2106:
2104:
2101:
2099:
2096:
2092:
2089:
2087:
2084:
2082:
2079:
2078:
2077:
2076:
2072:
2070:
2067:
2066:
2064:
2062:
2058:
2053:
2049:
2042:
2037:
2035:
2030:
2028:
2023:
2022:
2019:
2013:
2010:
2008:
2005:
2003:
2000:
1998:
1995:
1993:
1989:
1986:
1984:
1981:
1979:
1976:
1973:
1970:
1969:
1965:
1961:
1958:
1955:
1952:
1951:
1947:
1938:
1934:
1930:
1926:
1925:
1917:
1914:
1902:
1898:
1892:
1889:
1873:
1869:
1867:
1859:
1852:
1849:
1837:
1831:
1828:
1824:
1814:
1811:
1799:
1793:
1790:
1787:
1786:
1780:
1777:
1772:
1765:
1763:
1759:
1747:
1741:
1738:
1731:
1729:
1725:
1718:
1712:
1709:
1706:
1703:
1700:
1699:
1698:
1694:
1689:
1685:
1681:
1675:
1673:
1667:
1665:
1661:
1656:
1652:
1649:
1643:
1641:
1637:
1633:
1629:
1625:
1621:
1613:
1609:
1605:
1601:
1597:
1593:
1588:
1585:node.right ≠
1584:
1580:
1576:
1572:
1569:
1565:
1561:
1557:
1555:
1550:
1542:
1537:
1534:
1531:
1530:
1529:
1523:
1520:
1517:
1516:
1515:
1509:
1506:
1505:
1504:
1501:
1496:
1488:
1486:
1484:
1479:
1474:
1460:
1437:
1407:
1404:
1384:
1381:
1378:
1375:
1355:
1349:
1331:
1324:
1320:
1316:
1312:
1308:
1304:
1301:
1297:
1294:
1290:
1286:
1283:
1279:
1275:
1271:
1255:
1243:
1238:, either the
1233:
1230:The function
1226:
1222:
1218:
1214:
1210:
1206:
1202:
1198:
1194:
1191:
1187:
1183:
1177:
1161:
1157:
1153:
1149:
1145:
1141:
1137:
1133:
1129:
1125:
1119:
1111:
1107:
1103:
1100:
1096:
1092:
1089:
1086:
1082:
1079:
1075:
1071:
1067:
1063:
1060:
1056:
1052:
1048:
1047:
1041:
1033:
1029:
1026:
1022:
1018:
1014:
1010:
1007:
1003:
999:
996:
993:
989:
985:
982:
978:
974:
970:
966:
963:
959:
955:
951:
950:
944:
936:
932:
928:
925:node.right ≠
924:
920:
917:
913:
909:
906:
902:
898:
894:
890:
887:
883:
879:
875:
874:
868:
863:
855:
852:
844:
834:
830:
826:
820:
819:
815:
810:This section
808:
804:
799:
798:
792:
790:
788:
783:
781:
780:stack machine
777:
773:
770:
766:
763:
760:
756:
751:
749:
746:
742:
739:
735:
731:
727:
718:
714:
706:
702:
696:
691:
684:
682:
680:
676:
672:
664:
662:
660:
656:
650:
642:
638:
631:
629:
622:
619:
614:
611:
607:
606:
604:
600:
597:
594:
593:
592:
586:
584:
582:
578:
570:
567:
564:
563:
559:
554:
551:
548:
547:
543:
538:
535:
532:
531:
527:
525:
523:
519:
511:
508:
505:
504:
501:In-order, LNR
500:
498:
496:
492:
484:
481:
478:
477:
473:
471:
469:
461:
458:
455:
454:
450:
339:
338:
337:
333:
324:
321:
318:
317:
315:
312:
311:
310:
307:
305:
292:
285:
280:
273:
268:
261:
260:
256:
251:
243:
241:
238:
236:
232:
228:
224:
220:
211:
209:
207:
203:
199:
194:
193:breadth-first
190:
186:
182:
178:
170:
168:
166:
162:
158:
154:
150:
146:
142:
131:
128:
120:
109:
106:
102:
99:
95:
92:
88:
85:
81:
78: –
77:
73:
72:Find sources:
66:
62:
56:
55:
50:This article
48:
44:
39:
38:
33:
19:
2185:Bellman–Ford
2074:
2051:
1992:Rosetta Code
1928:
1922:
1916:
1905:. Retrieved
1901:Fekir's Blog
1900:
1891:
1879:. Retrieved
1872:the original
1864:
1851:
1839:. Retrieved
1830:
1813:
1801:. Retrieved
1792:
1784:
1779:
1770:
1749:. Retrieved
1740:
1723:
1719:
1716:
1692:
1688:compositions
1676:
1668:
1657:
1653:
1647:
1644:
1617:
1607:
1603:
1599:
1595:
1591:
1586:
1582:
1578:
1577:node.left ≠
1574:
1570:
1567:
1563:
1559:
1546:
1527:
1513:
1503:Advantages:
1502:
1498:
1475:
1327:
1322:
1318:
1314:
1310:
1306:
1302:
1299:
1295:
1292:
1288:
1284:
1281:
1277:
1273:
1270:further on.
1253:
1241:
1231:
1229:
1224:
1220:
1216:
1212:
1208:
1204:
1200:
1196:
1192:
1189:
1185:
1175:
1165:
1155:
1151:
1147:
1143:
1139:
1135:
1131:
1127:
1123:
1109:
1105:
1101:
1098:
1094:
1090:
1087:
1084:
1080:
1077:
1073:
1069:
1061:
1058:
1054:
1050:
1031:
1027:
1024:
1020:
1016:
1012:
1008:
1005:
1001:
997:
994:
991:
987:
983:
980:
976:
972:
964:
961:
957:
953:
934:
933:node.left ≠
930:
926:
922:
918:
915:
911:
907:
904:
900:
896:
888:
885:
881:
877:
847:
838:
823:Please help
811:
784:
776:machine code
771:
768:
764:
761:
758:
752:
747:
744:
740:
737:
733:
723:
716:
712:
704:
700:
694:
685:Applications
668:
658:
654:
652:
640:
626:
612:-th subtree.
609:
602:
590:
580:
574:
521:
515:
488:
465:
334:
330:
308:
303:
301:
286:
274:
262:
239:
215:
177:linked lists
174:
152:
148:
144:
138:
123:
114:
104:
97:
90:
83:
71:
59:Please help
54:verification
51:
2103:Beam search
2069:α–β pruning
1564:empty queue
1315:empty stack
1232:inorderNext
1225:empty stack
1190:empty stack
1085:empty stack
988:empty stack
912:empty stack
675:search tree
665:Other types
641:Level-order
231:corecursion
189:depth-first
165:binary tree
149:tree search
32:Search tree
2267:Categories
2190:Dijkstra's
1907:2021-08-15
1881:January 2,
1732:References
1707:(1, 1) (2)
1680:one-to-one
1478:call stack
1291:newnode =
1280:newnode ≠
581:descending
235:call stack
221:(LIFO) or
183:and other
87:newspapers
2283:Recursion
2233:Kruskal's
2228:Borůvka's
2200:Johnson's
1632:game tree
1596:procedure
1560:procedure
1382:−
1330:amortised
1274:procedure
1252:in-order-
1250:) or the
1240:in-order-
1186:procedure
1140:procedure
1128:procedure
1070:procedure
1051:procedure
973:procedure
954:procedure
897:procedure
878:procedure
841:June 2013
812:does not
657:(BFS) or
601:For each
522:ascending
227:recursion
2123:Parallel
1083:stack ←
986:stack ←
910:stack ←
437: I
433: I
417: I
117:May 2009
1948:Sources
1195:node ≠
1152:else if
1104:node ≠
1097:node ≠
1076:node =
1057:node =
1011:node ≠
1004:node ≠
979:node =
960:node =
903:node =
884:node =
833:removed
818:sources
728:) from
175:Unlike
101:scholar
2238:Prim's
2061:Search
1323:return
1307:return
1296:return
1256:cessor
1244:cessor
1217:return
1205:return
1176:search
1136:return
1081:return
1062:return
984:return
965:return
908:return
889:return
103:
96:
89:
82:
74:
2210:Yen's
2048:Graph
1875:(PDF)
1861:(PDF)
1841:2 May
1803:2 May
1751:2 May
1717:etc.
1636:chess
1568:while
1549:queue
1453:with
1319:until
1289:until
1264:stack
1260:dir=0
1258:(for
1254:prede
1248:dir=1
1246:(for
1193:while
1180:stack
1144:while
1132:while
1088:while
995:while
916:while
575:In a
516:In a
493:of a
223:queue
219:stack
206:below
200:like
171:Types
108:JSTOR
94:books
2167:SSS*
2091:SMA*
2086:LPA*
2081:IDA*
2052:tree
2050:and
1883:2016
1868:Math
1866:UCLA
1843:2015
1805:2015
1753:2015
1634:for
1604:from
1587:null
1579:null
1311:null
1293:null
1282:null
1236:node
1221:null
1213:else
1197:null
1168:node
1166:The
1156:else
1110:else
1106:null
1099:null
1078:null
1059:null
1032:else
1025:null
1017:else
1013:null
1006:null
992:null
981:null
962:null
935:null
927:null
905:null
886:null
816:any
814:cite
767:− *
151:and
80:news
1990:on
1933:doi
1726:− 1
1704:(1)
1695:≥ 1
1648:any
1638:or
1600:for
1571:not
1268:dir
1242:suc
1172:bst
1091:not
1028:and
998:not
919:not
827:by
677:on
653:In
302:In
191:or
139:In
63:by
2269::
2147:D*
2130:B*
2075:A*
1927:.
1899:.
1863:.
1761:^
1701:()
1640:go
1608:to
1606:0
1602:i
1583:if
1575:if
1556:.
1313:,
1303:if
1300:do
1285:do
1278:if
1227:)
1223:,
1209:if
1201:if
1148:if
1138:i
1102:if
1095:or
1074:if
1055:if
1021:if
1009:if
1002:or
977:if
958:if
931:if
923:if
901:if
882:if
743:+
736:−
715:+
709:+
703:−
697:*
497:.
237:.
208:.
179:,
143:,
2040:e
2033:t
2026:v
1939:.
1935::
1929:9
1910:.
1885:.
1845:.
1807:.
1755:.
1724:n
1693:n
1664:ω
1461:h
1441:)
1438:h
1435:(
1430:O
1408:,
1405:n
1385:2
1379:n
1376:2
1356:,
1353:)
1350:1
1347:(
1342:O
1309:(
1219:(
854:)
848:(
843:)
839:(
835:.
821:.
772:E
769:D
765:C
762:B
759:A
748:E
745:D
741:C
738:B
734:A
719:)
717:E
713:D
711:(
707:)
705:C
701:B
699:(
695:A
610:i
603:i
445:F
443:-
441:G
439:-
435:-
431:-
429:H
427:-
425:H
423:-
421:H
419:-
415:-
413:G
411:-
409:G
407:-
405:F
403:-
401:B
399:-
397:D
395:-
393:E
391:-
389:E
387:-
385:E
383:-
381:D
379:-
377:C
375:-
373:C
371:-
369:C
367:-
365:D
363:-
361:B
359:-
357:A
355:-
353:A
351:-
349:A
347:-
345:B
343:-
341:F
293::
291:)
289:●
281::
279:)
277:●
269::
267:)
265:●
130:)
124:(
119:)
115:(
105:·
98:·
91:·
84:·
57:.
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
