Morris traversal - how to check if you reach leaf nodes?

Question

In the morris traversal of a binary tree, it uses every right leaf node to build the connection towards the current node.

Suppose we are traversing the tree in the preorder way, when reaching the leaf nodes, how can we judge if we meet the leaf nodes?

eg. we cannot use the following line to check: if (null == node.left && null == node.right)

because here node.right is pointing to the current node because of the morris algorithm.

One good way is that we always mark the nodes visited as visited, using a field in the TreeNode object, but what if we do not have this field, as in many cases?

Anyone has the idea how to check if you reach leaf nodes? Thanks.

Regards, Jack

Answer 1

Like Jack has answered, it's to check if if (null == node.left && (null == node.right || node.right.isLinked). In python, you can setattr for predecessor before linking it to curr.

Share my code here

def getLeaf(self, root):
    curr = root
    while curr != None:
        if not curr.left and (not curr.right or hasattr(curr, 'isLinked')):
            print("I am a leaf ", curr.val)
        if curr.left is None:
            curr = curr.right
        else:
            prec = curr.left
            while prec.right != None and prec.right != curr:
                prec = prec.right
            if prec.right is None:
                prec.right = curr
                setattr(prec, 'isLinked', True)
                curr = curr.left
            else:
                curr = curr.right

Answer 2

UPDATE: I came up with cleaner explanation on how to detect leaf nodes with Morris Traversal. All leafs are:

1. Exactly one leaf is the most right one on the tree. To detect it, you need to check for curr left == nil and curr.right == nil
2. All the rest of leafs are the ones with artificially setup links to other nodes. If you think about it, it makes sense: Morris Traversal cannot backtrack in any other ways from leaf nodes. Therefore, all the rest of leafs are the predecessors are/were connected to current node.

If it still does not make sense to you, look at this visualization of the Morris Traversal and note that all but one leafs are 'connected' nodes + one in the very end of the tree:

---

It's tricky, but possible, here is code in Go that I tested with a ton of tricky edge cases while still maintaining O(1):

func getLeafs(node *TreeNode) []int {
    var leafs []int
    var pre *TreeNode // predecessor of the current node
    curr := node

    for curr != nil {
        if curr.Left == nil {
            if curr.Right == nil { // additional check needed
                leafs = append(leafs, curr.Val)
            }
            curr = curr.Right
            continue
        }

        // curr.Right != nil
        pre = curr.Left
        for pre.Right != nil && pre.Right != curr {
            pre = pre.Right
        }

        if pre.Right == nil {
            pre.Right = curr
            curr = curr.Left
            continue
        }

        // pre.Right == curr
        pre.Right = nil
        if pre.Left == nil { // tricky part! we are not using curr here
            leafs = append(leafs, pre.Val)  // we are actually using pre
        }
        curr = curr.Right
    }

    return leafs
}

Basically, you need to check in two places:

1. As in the standard Morris traversal, you check if the curr.Left == nil and then curr.Right == nil
2. Tricky part: instead of using curr, you need to work with pre nodes when they have the link to the currnode.

Answer 3

The problem can be simply solved by marking the nodes that have been visited.

So a leaf node can be justified by: if (null == node.left && (null == node.right || node.right.isLinked)) where "isLinked" is the nodes that is linked by the every right leaf nodes because of the Morris algorithm.

Ok, it goes back to my question again, how can we have this record about "isLinked"?

We can easily solve it by having a set to add all morris-linked nodes.

So it would be: if ((null == node.left && null == node.right) || set.contains(node.right))