Editing Binary tree (section)

=== Traversal ===
{{Main|Tree traversal}}

Pre-order, in-order, and post-order traversal visit each node in a tree by recursively visiting each node in the left and right subtrees of the root. Below are the brief descriptions of above mentioned traversals.

==== Pre-order ====
In pre-order, we always visit the current node; next, we recursively traverse the current node's left subtree, and then we recursively traverse the current node's right subtree. 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.

==== In-order ====
In in-order, we always recursively traverse the current node's left subtree; next, we visit the current node, and lastly, we recursively traverse the current node's right subtree.

==== Post-order ====
In post-order, we always recursively traverse the current node's left subtree; next, we recursively traverse the current node's right subtree and then visit the current node. Post-order traversal can be useful to get postfix expression of a [[binary expression tree]].<ref>{{Cite web |date=2015-02-13 |first=Todd |last=Wittman |title=Lecture 18: Tree Traversals |url=http://www.math.ucla.edu/~wittman/10b.1.10w/Lectures/Lec18.pdf |access-date=2023-04-29 |archive-url=https://web.archive.org/web/20150213195803/http://www.math.ucla.edu/~wittman/10b.1.10w/Lectures/Lec18.pdf |archive-date=2015-02-13 }}</ref>

==== Depth-first order ====
In depth-first order, we always attempt to visit the node farthest from the root node that we can, but with the caveat that it must be a child of a node we have already visited. Unlike a depth-first search on graphs, there is no need to remember all the nodes we have visited, because a tree cannot contain cycles. Pre-order is a special case of this. See [[depth-first search]] for more information.

==== Breadth-first order ====
Contrasting with depth-first order is breadth-first order, which always attempts to visit the node closest to the root that it has not already visited. See [[breadth-first search]] for more information. Also called a ''level-order traversal''.

In a complete binary tree, a node's breadth-index (''i'' − (2<sup>''d''</sup> − 1)) can be used as traversal instructions from the root. Reading bitwise from left to right, starting at bit ''d'' − 1, where ''d'' is the node's distance from the root (''d'' = ⌊log{{sub|2}}(''i''+1)⌋) and the node in question is not the root itself (''d'' > 0). When the breadth-index is masked at bit ''d'' − 1, the bit values {{mono|0}} and {{mono|1}} mean to step either left or right, respectively. The process continues by successively checking the next bit to the right until there are no more. The rightmost bit indicates the final traversal from the desired node's parent to the node itself. There is a time-space trade-off between iterating a complete binary tree this way versus each node having pointer(s) to its sibling(s).