Tree Traversals

Morris traversal, iterator pattern, and serialization.

7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Morris Traversal (O(1) Space)

Morris traversal achieves inorder without stack/recursion by temporarily threading tree. Find predecessor, link to current, traverse left, then remove link.

Gomorris-inorder-traversal.go

30 linesLn 1, Col 1Go

If left exists, find rightmost node in left subtree (predecessor). If predecessor's right is nil, thread to current and go left. If threaded, remove thread, visit current, go right. O(1) space, O(n) time.

BST Iterator

Implement iterator over BST with next() and hasNext() in O(1) amortized. Use controlled inorder traversal with stack. Partial traversal on demand.

Gobst-iterator.go

28 linesLn 1, Col 1Go

Stack simulates inorder recursion state. Constructor pushes left spine. Next() pops, visits, pushes left spine of right child. Average O(1) per call.

Serialization/Deserialization

Convert tree to string and back. Preorder with 'null' markers is standard. Deserialize using queue/index to rebuild.

Goserialize-and-deserialize.go

25 linesLn 1, Col 1Go

Preorder: root, left, right. 'null' marks empty children. Deserialize uses same preorder: read val, build left, build right. Index tracks position in split array.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.