algorithm-notes
  • Preface
  • Outline
    • Asymptotic-Analysis
    • Divide-and-Conquer (DnC)
      • Overview
      • Multiplication
      • DnC Strategy
      • Master Method
    • Randomization
      • Overview
      • Discrete Probability
      • Randomized Algorithms
      • Reservoir Sampling
    • Sorting
      • Overview
      • Selection Sort
      • Bubble Sort
      • Insertion Sort
      • Shell Sort
      • Merge Sort
      • Heap Sort
      • Quick Sort
      • Non-Comparison Sort
    • Graph Algorithms
      • Overview
      • Minimum Spanning Tree
      • Shortest Path
      • Topological Sort
    • Tree
      • Overview
      • Balanced Search Tree
        • AVL Tree
        • Red-Black Tree
        • B Tree
      • Heap
      • Disjoint Set
      • Threaded Binary Tree
      • Segment Tree
    • Searching
      • Overview
      • Binary Search
      • Graph Search
      • Hash Table
      • String Search
    • Dynamic Programming
      • Overview
      • Fibonacci Numbers
      • LCS problem
    • Greedy Algorithms
      • Overview
Powered by GitBook
On this page
  • In-order Morris Traversal
  • Basic Ideas
  • Complexity

Was this helpful?

  1. Outline
  2. Tree

Threaded Binary Tree

PreviousDisjoint SetNextSegment Tree

Last updated 6 years ago

Was this helpful?

Unlike which adopts recursive algorithms to traverse a tree before backtracking (the stack space of recursive calls would be Ο(n)) and unlike which needs a queue to help traverse the tree level by level, can achieve traversing a binary tree with only Ο(1) extra space allowed. The traverse method adopting Threaded Binary Tree is also called Morris Traversal.

That said, we do not need to allocate additional memory for each node in the tree. Only using the left and right null pointers of leaves to point to some predecessors or successors would be necessary, which also maintains the original tree structure intact. In a standard Morris traversal algorithm, there is only an in-order version and this chapter only introduces that version. Further modifications could be explored by the users.

In-order Morris Traversal

Basic Ideas

Given a binary tree and its root node, the steps of the traversal algorithm includes:

  1. If current node's left child is null, output the current node's value and set its right child as the new current node.

  2. Else if current node's left child is not null, then try to find the predecessor for current node's left subtree in the in-order traversal.

    • 2-1 If the right child of this predecessor is null, set it to current node and update new current node to be the left child of current node.

    • 2-2 Else if the right child of this predecessor is the current node, reset the right child to null (same as recover the original tree structure) and output the current node.

repeat step 1 and 2 until current node is null.

Figure 1. In-order Morris Traversal Demonstration

Complexity

There are only two additional pointers used, thus requires only Ο(1) for space. Time complexity is Ο(n) since the number of searches for all predecessors of all nodes is bounded by c × n (a binary tree with n nodes has no more then n - 1 nodes, every edge is traversed at most twice).

In the following figure where red dotted lines denote the process of finding such nodes while black dotted lines denote the process of finding predecessors.

Figure 2. Total number of searches

DFS
BFS
Threaded Binary Tree