Editing Binary tree (section)

== Common operations ==
[[File:BinaryTreeRotations.svg|thumb|300px|[[Tree rotation]]s are very common internal operations on [[Self-balancing binary search tree|self-balancing binary trees]].]]
There are a variety of different operations that can be performed on binary trees. Some are [[mutator method|mutator]] operations, while others simply return useful information about the tree.

=== Insertion ===
Nodes can be inserted into binary trees in between two other nodes or added after a [[leaf node]]. In binary trees, a node that is inserted is specified as to whose child it will be.

==== Leaf nodes ====
To add a new node after leaf node A, A assigns the new node as one of its children and the new node assigns node A as its parent.

==== Internal nodes ====
[[File:Insertion of binary tree node.svg|thumb|360px|The process of inserting a node into a binary tree]]
Insertion on [[internal node]]s is slightly more complex than on leaf nodes. Say that the internal node is node A and that node B is the child of A. (If the insertion is to insert a right child, then B is the right child of A, and similarly with a left child insertion.) A assigns its child to the new node and the new node assigns its parent to A. Then the new node assigns its child to B and B assigns its parent as the new node.

=== Deletion ===
Deletion is the process whereby a node is removed from the tree.  Only certain nodes in a binary tree can be removed unambiguously.<ref name="rice">{{cite web |url=http://www.clear.rice.edu/comp212/03-spring/lectures/22/|title=Binary Tree Structure| author=Dung X. Nguyen|year=2003|publisher=rice.edu|access-date=December 28, 2010}}
</ref>

==== Node with zero or one children ====
[[File:Deletion of internal binary tree node.svg|thumb|360px|The process of deleting an internal node in a binary tree]]
Suppose that the node to delete is node A. If A has no children, deletion is accomplished by setting the child of A's parent to [[null pointer|null]]. If A has one child, set the parent of A's child to A's parent and set the child of A's parent to A's child.

==== Node with two children ====
In a binary tree, a node with two children cannot be deleted unambiguously.<ref name="rice"/> However, in certain binary trees (including [[binary search tree]]s) these nodes ''can'' be deleted, though with a rearrangement of the tree structure.

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