4

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?

Joris Schellekens
  • 8,483
  • 2
  • 23
  • 54
Invariance
  • 313
  • 6
  • 16
  • 2
    Take a stab at it and see what happens. – wwii Aug 31 '17 at 13:27
  • You can use recursion on the tuple form, as well. – tobias_k Aug 31 '17 at 13:33
  • As long as you have memory, I'd assume infinite, but the recursive function to find the depth could hit python's recursion limit (which you can change in settings). Converting it to an iterative function, maybe by using a stack, is a better solution to that issue. – Kenny Ostrom Aug 31 '17 at 13:40
  • [What have you tried](http://idownvotedbecau.se/noattempt/) ? Show us your [attempted code](https://stackoverflow.com/help/on-topic), and [what went wrong](https://stackoverflow.com/help/how-to-ask) with that. Then we can help you *debug* or offer a different approach. – SherylHohman Dec 20 '17 at 19:00

4 Answers4

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

Right leg
  • 16,080
  • 7
  • 48
  • 81
2

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

Joris Schellekens
  • 8,483
  • 2
  • 23
  • 54
1

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
Yilmaz
  • 35,338
  • 10
  • 157
  • 202
0
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