CODEWITHSUNDEEP
pythontuplesbinary-tree
Invariance
Invariance

Reputation: 313

Maximum depth of a binary tree in python

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?

Upvotes: 4

Views: 3229

Answers (4)

Yilmaz
Yilmaz

Reputation: 49321

I solve this with level order traversal. If you know level order traversal, this question and https://leetcode.com/problems/binary-tree-right-side-view/ question can be solved with same technique:

from collections import deque
class Solution:
    def max_depth(self,root):
        if not root:
            return 0
        level=0
        q=deque([root])
        while q:
            # once we exhaust the for loop, that means we traverse all the nodes in the same level
            # so after for loop increase level+=1
            for i in range(len(q)):
                node=q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            level+=1
        return level

Upvotes: 1

user8459437
user8459437

Reputation: 

class Node(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
   def maxDepth(self, root):
      if not root:
          return 0
      ldepth = self.maxDepth(root.left)
      rdepth = self.maxDepth(root.right)
      return max(ldepth, rdepth) + 1

Upvotes: 0

Joris Schellekens
Joris Schellekens

Reputation: 9022

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

Upvotes: 2

Right leg
Right leg

Reputation: 16720

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).

Upvotes: 2

Related Questions