Most commonly used tree traversal algorithms use O(h) space, with h the height of the tree. By applying Morris algorithm, it allows to traverse a tree with O(1) space. Below is an inorder traversal algorithm which adds up the value of all the leaf nodes.
Given a binary tree, find the sum of all leaf nodes.
# Morris inorder class Solution: """ @param root: @return: the sum of leafnode """ def sumLeafNode(self, root): res = 0 p = root while p: if p.left is None: if p.right is None: # p is a leaf node res += p.val p = p.right else: tmp = p.left while tmp.right is not None and tmp.right != p: tmp = tmp.right if tmp.right is None: if tmp.left is None: # tmp is a leaf node res += tmp.val tmp.right = p p = p.left else: tmp.right = None p = p.right return res