Recursive Binary Tree Inorder Traversal in Python

Question

This is a very simple problem to see if my understanding of basic Python is correct

Problem:

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]

Output: [1,3,2]

Solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.inorder = []
        self.inorderHelper(root, self.inorder)
        return self.inorder
    
    def inorderHelper(self, node, inorder):
        if (node is None): 
            return
        else:
            self.inorderHelper(node.left, inorder)
            inorder.append(node.val)
            self.inorderHelper(node.right, inorder)
    

Answer 1

Naming

Solution is a bit generic for a class name. It could basically mean anything, because almost every algorithm has some kind of solution. A better fitting name would be TreeTraversal. It tells the reader (you, but also others) what it means.

inorderTraversal has two problems. Firstly, it doesn't sound like a method name, because methods are usually verbs. Secondly, the convention for methods and functions in Python is lower_case_with_underscores, also called snake case. My suggestion is to name it traverse_inorder, or even just inorder considering you rename the class to TreeTraversal.

inorderHelper has the same two problems as the previous one, but additionally it does not really tell you what it does. If it is a helper, maybe it should be a class, but it does not do enough for that. If it is a method or function, what does it help you with, i. e. what does it do? A better name might be traverse, and you could consider making it an inner method of the other method, since it will not be used outside of it. That way the user of the class does not need to think about which one of the two methods to use.

OOP

You might consider making all that code (after the suggested changes above, only one short method) part of the tree class. After all, it depends on the tree anyways. Of course this does not apply if you did not write the Tree class yourself, or if you want to make a more generic traversal class for different types of trees.

In def inorderHelper(self, node, inorder) you do not need to specify a parameter for inorder. Since it is a member variable, you can just access it via self.inorder.

---

def inorderHelper(self, node, inorder):
    if (node is None): 
        return
    else:
        self.inorderHelper(node.left, inorder)
        inorder.append(node.val)
        self.inorderHelper(node.right, inorder)

You can invert the if-condition and thus make the code shorter. The else is implicit. The parantheses around the condition are not needed and usually not used, since without them it reads more naturally.

def inorderHelper(self, node, inorder):
    if node is not None:
        self.inorderHelper(node.left, inorder)
        inorder.append(node.val)
        self.inorderHelper(node.right, inorder)