Editing Tree traversal (section)

====Morris in-order traversal using threading====
{{main|Threaded binary tree}}
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).

Advantages:
# Avoids recursion, which uses a call stack and consumes memory and time.
# The node keeps a record of its parent.

Disadvantages:
# The tree is more complex.
# We can make only one traversal at a time.
# It is more prone to errors when both the children are not present and both values of nodes point to their ancestors.

Morris traversal is an implementation of in-order traversal that uses threading:<ref>{{Cite journal | doi = 10.1016/0020-0190(79)90068-1| title = Traversing binary trees simply and cheaply| journal = [[Information Processing Letters]]| volume = 9| issue = 5| year = 1979| last1 = Morris | first1 = Joseph M.| pages = 197–200}}</ref>
# Create links to the in-order successor.
# Print the data using these links.
# Revert the changes to restore original tree.