Maximum depth of a binary tree in python

Question

I created a tuple from a binary tree and it looks like this:

tuple = (1,(2,(4,5,6),(7,None,8)),(3,9,(10,11,12)))

The tree structure becomes more clear by applying indentation:

 (1,  
    (2,
        (4,
            5,
            6
        ),
        (7,
            None,
            8
        )
    ),
    (3,
        9,
        (10,
            11,
            12
        )
    )
)

I know how to find the maximum depth of the binary tree using recursive method, but I am trying to find the maximum depth using the tuple I created. Can anyone help me with how to do it?

Answer 1

Recursive method:

a = (1,(2,(4,5,6),(7,None,8)),(3,9,(10,11,12)));

def depth(x):
    if(isinstance(x, int) or x == None):
        return 1;
    else:
        dL = depth(x[1]);
        dR = depth(x[2]);
        return max(dL, dR) + 1;

print(depth(a));

The idea is to determine the depth of a tree by looking at its left and right subtree. If the node does not have subtrees, a depth of 1 is returned. Else it returns max(depth of right, depth of left) + 1

Answer 2

Here is a tricky but rather efficient solution, that will work, provided no elements of your data structure is a string containing '(' or ')'. I would convert the tuple to a string, and parse it so as to count the depth of the parentheses.

string = str(myTuple)

currentDepth = 0
maxDepth = 0
for c in string:
    if c == '(':
        currentDepth += 1
    elif c == ')':
        currentDepth -= 1

    maxDepth = max(maxDepth, currentDepth)

It gives the depth in a linear time with regards to the number of characters in the string into which the tuple was converted. That number should be more or less proportional to the number of elements plus the depth, so you'd have a complexity somewhat equal to O(n + d).