My iterative solution using O(n) time and O(1) space


  • 0
    G

    This is an iterative solution using O(n) time and O(1) space.

    The idea is based on the Morris Traversal,
    which is probably the most famous stackless algorithm for traversing binary trees.
    The Morris Traversal is O(n) time because each edge is traversed at most 3 times.
    The Morris Traversal is O(1) space because it doesn't use stacks or recursive calls.

    Consider using the Morris Traversal to traverse the tree in an "in-order" style as follows:

    void inorderTraversal(struct TreeNode *root) {
        struct TreeNode *curr = root;
        while (curr) {
            if (curr->left) {
                struct TreeNode *pred = curr->left;
                while (pred->right && pred->right != curr) {
                    pred = pred->right;
                }
                if (!pred->right) {
                    /* we haven't visit curr->left */
                    pred->right = curr;
                    curr = curr->left;
                    continue;
                }
                /* we are coming from pred */
                pred->right = NULL;
            }
            printf("Visit node %d here\n", curr->val);
            curr = curr->right;
        }
    }
    

    The original Morris Traversal won't track the depth of the current node.
    Fortunately, tracking the current depth is easy:

    • When we decide to move to curr->left, we should currDepth++.

    • When we decide to move to curr->right,
      because we don't know whether curr->right is a child or an ancestor,
      we just assume curr->right is a child, and we currDepth++.

      However, we need to check if we're wrong after moving to curr->right.

    • After moving to a node, if we found that we are coming from pred,
      we know that our previous currDepth++ operation is wrong.

      To fix it, we first currDepth-- to get the predecessor's depth,
      and use the distance between the current node and the predecessor
      to get the correct depth of the current node.

    Therefore, we can enhance the in-order Morris Traversal as follows:

    void inorderTraversal(struct TreeNode *root) {
        struct TreeNode *curr = root;
        int currDepth = root ? 1 : 0;
        while (curr) {
            if (curr->left) {
                struct TreeNode *pred = curr->left;
                int deltaDepth = 1; /* between curr and pred */
                while (pred->right && pred->right != curr) {
                    pred = pred->right;
                    deltaDepth++;
                }
                if (!pred->right) {
                    /* we haven't visit curr->left */
                    pred->right = curr;
                    curr = curr->left;
                    currDepth++;
                    continue;
                }
                /* we are coming from pred */
                pred->right = NULL;
                currDepth--; /* rollback to pred's depth */
                currDepth -= deltaDepth;
            }
            printf("Visit node %d (at depth=%d) here\n",
                   curr->val, currDepth);
            curr = curr->right;
            currDepth++;
        }
    }
    

    Using above codes to find the maximum depth is easy:
    Each time when we visit a node,
    we simply record the maximum value of currDepth.

    The final solution is as follows:

    int maxDepth(struct TreeNode *root) {
        int ans = 0;
        struct TreeNode *curr = root;
        int currDepth = root ? 1 : 0;
        while (curr) {
            if (curr->left) {
                struct TreeNode *pred = curr->left;
                int deltaDepth = 1; /* between curr and pred */
                while (pred->right && pred->right != curr) {
                    pred = pred->right;
                    deltaDepth++;
                }
                if (!pred->right) {
                    /* we haven't visit curr->left */
                    pred->right = curr;
                    curr = curr->left;
                    currDepth++;
                    continue;
                }
                /* we are coming from pred */
                pred->right = NULL;
                currDepth--; /* rollback to pred's depth */
                currDepth -= deltaDepth;
            }
            if (currDepth > ans) {
                ans = currDepth;
            }
            curr = curr->right;
            currDepth++;
        }
        return ans;
    }
    

    Compared to the original Morris Traversal,
    this solution just track additional 3 variables (ans, currDepth, deltaDepth),
    and won't affect the original code flow,
    so this solution is still O(n) time and O(1) space.


  • 0
    G

    For people not familiar with the Morris Traversal,
    I found some high-quality illustrations at Annie Kim's blog.
    Although her article is written in Chinese,
    her excellent illustrations are easy to understand even if you can't read Chinese.

    See the following example of performing the Morris Traversal in an "in-order" style:
    0_1483902653453_inorderMorrisTraversal.jpg

    void inorderTraversal(struct TreeNode *root) {
        struct TreeNode *curr = root;
        while (curr) {
            if (curr->left) {
                struct TreeNode *pred = curr->left;
                while (pred->right && pred->right != curr) {
                    pred = pred->right;
                }
                if (!pred->right) {
                    /* we haven't visit curr->left */
                    pred->right = curr;
                    curr = curr->left;
                    continue;
                }
                /* we are coming from pred */
                pred->right = NULL;
            }
            printf("Visit node %d here\n", curr->val);
            curr = curr->right;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.