94. Binary Tree Inorder Traversal

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def inorderTraversal(self, root): res = [] # list to store results ptr = root # pointer to elements in the tree history = [] # use as a stack while (done == False): while (ptr.left != None): history.append(ptr) ptr = ptr.left # now reached the leftmost element of the full tree curr = history.pop() res.append(curr.val) # prints out the leftmost element history.append(curr.right) ptr = curr while(ptr.left != None): history.append(ptr) ptr = ptr.left