<jupyter_start><jupyter_text>Generic Tree Node<jupyter_code>class TreeNode:
    def __init__(self,data):
        self.data=data
        self.children=list()

n1=TreeNode(5)
n2=TreeNode(2)
n3=TreeNode(9)
n4=TreeNode(8)
n5=TreeNode(17)
n6=TreeNode(15)
n7=TreeNode(1)

n1.children.append(n2)
n1.children.append(n3)
n1.children.append(n4)
n1.children.append(n5)

n3.children.append(n6)
n3.children.append(n7)<jupyter_output><empty_output><jupyter_text>Print Tree(Recursively)<jupyter_code>class TreeNode:
    def __init__(self,data):
        self.data=data
        self.children=list()

def printTree(root):
    #TNot a base case
    if root==None:
        return
    print(root.data)
    for child in root.children:
        printTree(child)

def printTreeDetailed(root):
    if root==None:
        return
    
    print(root.data,":",end=" ")
    for child in root.children:
        print(child.data,",",end=" ")
    print()
    
    for child in root.children:
        printTreeDetailed(child)


n1=TreeNode(5)
n2=TreeNode(2)
n3=TreeNode(9)
n4=TreeNode(8)
n5=TreeNode(7)
n6=TreeNode(15)
n7=TreeNode(1)

n1.children.append(n2)
n1.children.append(n3)
n1.children.append(n4)
n1.children.append(n5)

n3.children.append(n6)
n3.children.append(n7)
printTreeDetailed(n1)<jupyter_output><empty_output><jupyter_text>Take Tree Input(Recursively)<jupyter_code>class TreeNode:
    def __init__(self,data):
        self.data=data
        self.children=list()

def printTree(root):
    #TNot a base case
    if root==None:
        return
    print(root.data)
    for child in root.children:
        printTree(child)

def printTreeDetailed(root):
    if root==None:
        return
    
    print(root.data,":",end="")
    for child in root.children:
        print(child.data,",",end="")
    print()
    
    for child in root.children:
        printTreeDetailed(child)

def takeTreeInput():
    print('Enter Root Data')
    rootData=int(input())
    if rootData==-1:
        return None
    
    root=TreeNode(rootData)
    
    print('Enter number of children for',rootData)
    childrenCount=int(input())
    for i in range(childrenCount):
        child=takeTreeInput()
        root.children.append(child)
    return root

root=takeTreeInput()
printTreeDetailed(root)<jupyter_output><empty_output><jupyter_text>Number Of Nodes In Generic Tree<jupyter_code>class TreeNode:
    def __init__(self,data):
        self.data=data
        self.children=list()

def printTree(root):
    #TNot a base case
    if root==None:
        return
    print(root.data)
    for child in root.children:
        printTree(child)

def printTreeDetailed(root):
    if root==None:
        return
    
    print(root.data,":",end="")
    for child in root.children:
        print(child.data,":",end="")
    print()
    
    for child in root.children:
        printTreeDetailed(child)

def takeTreeInput():
    print('Enter Root Data')
    rootData=int(input())
    if rootData==-1:
        return None
    
    root=TreeNode(rootData)
    
    print('Enter number of children for',rootData)
    childrenCount=int(input())
    for i in range(childrenCount):
        child=takeTreeInput()
        root.children.append(child)
    return root

def numNodes(root):
    if root==None:
        return 0
    count=1
    for child in root.children:
        count=count+numNodes(child)
    return count

root=takeTreeInput()
printTreeDetailed(root)
print(numNodes(root))<jupyter_output><empty_output><jupyter_text>Sum of all nodes    Given a generic tree, find and return the sum of all nodes present in the given tree.    Input format :    The first line of input contains data of the nodes of the tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.       Output Format :    The first and only line of output prints the sum of all nodes of the given generic tree.    Constraints:    Time Limit: 1 sec    Sample Input 1:    10 3 20 30 40 2 40 50 0 0 0 0     Sample Output 1:    190<jupyter_code>import sys
import queue

class TreeNode :
    def __init__(self, data) :
        self.data = data
        self.children = list()

def inputLevelWise(li) :
    i = 0
    data = li[i] 
    i += 1
    if data == -1 :
        return None
    root = TreeNode(data) 
    q = queue.Queue()
    q.put(root)
    while (not q.empty()) :
        frontNode = q.get()
        noOfChildren = li[i]
        i += 1
        childrenArray = li[i : i+noOfChildren]
        for childData in childrenArray :
            childNode = TreeNode(childData)
            frontNode.children.append(childNode)
            q.put(childNode)
        i = i+noOfChildren
    return root
        
def sumOfAllNodes(root) :
    #############################
    # PLEASE ADD YOUR CODE HERE #
    #############################
    if root is None:
        return 0
    sum=root.data
    for i in root.children:
       sum+= sumOfAllNodes(i)
    return sum
    
#main
sys.setrecursionlimit(10**6)
li = [int(elem) for elem in list(input().strip().split())]
root = inputLevelWise(li)
print(sumOfAllNodes(root))<jupyter_output><empty_output><jupyter_text>Node With Largest Data    Given a generic tree, find and return the node with maximum data. You need to return the node which is having maximum data.    Return null if tree is empty.    Input format :    The first line of input contains data of the nodes of the tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.    Output Format :    The first and only line of output contains the data of the node with largest data in the given tree.    Constraints:    Time Limit: 1 sec    Sample Input 1:    10 3 20 30 40 2 40 50 0 0 0 0     Sample Output 1:    50<jupyter_code>from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)
class treeNode:
    def __init__(self, data):
        self.data = data
        self.children = []
    def __str__(self):
        return str(self.data)
max = None
def maxDataNode(root):
    #############################
    # PLEASE ADD YOUR CODE HERE #
    #############################
    global max
  
    if (root is None):
        return
 

    # If max is null, return the value of root node
    
    if ((max) == None):
        max = root
 
    # If value of the root is greater than max, update the max node
    
    elif (root.data > (max).data):
        max = root
 
    # Recursively call for all the children of the root node
    
    for i in root.children:
        maxDataNode(i)
        
    return max

def createLevelWiseTree(arr):
    root = treeNode(int(arr[0]))
    q = [root]
    size = len(arr)
    i = 1
    while i<size:
        parent = q.pop(0)
        childCount = int(arr[i])
        i += 1
        for j in range(0,childCount):
            temp = treeNode(int(arr[i+j]))
            parent.children.append(temp)
            q.append(temp)
        i += childCount
    return root

# Main
arr = list(int(x) for x in stdin.readline().rstrip().rsplit())
tree = createLevelWiseTree(arr)
print(maxDataNode(tree).data)<jupyter_output><empty_output><jupyter_text>Height Of Tree    Given a generic tree, find and return the height of given tree.    Input Format:    The first line of input contains data of the nodes of the tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.      Output Format :    The first and only line of output prints the height of the given generic tree.    Constraints:    Time Limit: 1 sec    Sample Input 1:    10 3 20 30 40 2 40 50 0 0 0 0     Sample Output 1:    3<jupyter_code>from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)
## Read input as specified in the question.
## Print output as specified in the question.
class TreeNode :
    def __init__(self, data) :
        self.data = data
        self.children = list()
max_=None

def maxHeight(root):
    
    if root is None:
        return 0
   
    max_=0
    
    for i in root.children:
        max_=max(max_,maxHeight(i))
    max_+=1

    return max_

import queue
def inputLevelWise(li) :
    i = 0
    data = li[i] 
    i += 1
    if data == -1 :
        return None
    root = TreeNode(data) 
    q = queue.Queue()
    q.put(root)
    while (not q.empty()) :
        frontNode = q.get()
        noOfChildren = li[i]
        i += 1
        childrenArray = li[i : i+noOfChildren]
        for childData in childrenArray :
            childNode = TreeNode(childData)
            frontNode.children.append(childNode)
            q.put(childNode)
        i = i+noOfChildren
    return root

li = [int(elem) for elem in list(input().strip().split())]
root = inputLevelWise(li)
print(maxHeight(root))<jupyter_output><empty_output><jupyter_text>Tree Input Levelwise<jupyter_code>class TreeNode:
    def __init__(self,data):
        self.data=data
        self.children=list()

def printTree(root):
    #TNot a base case
    if root==None:
        return
    print(root.data)
    for child in root.children:
        printTree(child)

def printTreeDetailed(root):
    if root==None:
        return
    
    print(root.data,":",end="")
    for child in root.children:
        print(child.data,",",end="")
    print()
    
    for child in root.children:
        printTreeDetailed(child)

def takeTreeInput():
    print('Enter Root Data')
    rootData=int(input())
    if rootData==-1:
        return None
    
    root=TreeNode(rootData)
    
    print('Enter number of children for',rootData)
    childrenCount=int(input())
    for i in range(childrenCount):
        child=takeTreeInput()
        root.children.append(child)
    return root

import queue
def takeTreeInputLevelWise():
    q=queue.Queue()
    print("Enter root")
    rootData=int(input())
    if rootData==-1:
        return None
    root=TreeNode(rootData)
    q.put(root)
    while(not(q.empty())):
        current_node=q.get()
        print("Enter num of children for",current_node.data)
        numChildren=int(input())
        for i in range(numChildren):
            print("Enter next child for",current_node.data)
            childData=int(input())
            child=TreeNode(childData)
            current_node.children.append(child)
            q.put(child)
    return root

def numNodes(root):
    if root==None:
        return 0
    count=1
    for child in root.children:
        count=count+numNodes(child)
    return count

root=takeTreeInputLevelWise()
printTreeDetailed(root)
print(numNodes(root))<jupyter_output><empty_output><jupyter_text>Print Levelwise    Given a generic tree, print the input tree in level wise order.    For printing a node with data N, you need to follow the exact format -    N:x1,x2,x3,...,xn    where, N is data of any node present in the generic tree. x1, x2, x3, ...., xn are the children of node N. Note that there is no space in between.    You need to print all nodes in the level order form in different lines.    Input format :    The first line of input contains data of the nodes of the tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.    Output Format :    The first and only line of output contains the elements of the tree in level wise order, as described in the task.    Constraints:    Time Limit: 1 sec    Sample Input 1:    10 3 20 30 40 2 40 50 0 0 0 0     Sample Output 1:    10:20,30,40    20:40,50    30:    40:    40:    50:<jupyter_code>import sys
class treeNode:
    def __init__(self, data):
        self.data = data
        self.children = []
    def __str__(self):
        return str(self.data)

def printLevelWiseTree(root):
    #############################
    # PLEASE ADD YOUR CODE HERE #
    #############################

        
    if (root == None):
        return
   
    q = []  
    q.append(root) # Enqueue root
    while (len(q) != 0):
            p = q[0]
            q.pop(0)
            print('%d:'%p.data,end="")
            length = len(p.children)
            # Enqueue all children of the dequeued item
            for i in range(length):
                if i<length-1:
                    print('%d,'%p.children[i].data,end="")
                else:
                    print('%d'%p.children[i].data,end="")
                q.append(p.children[i])
            print()

def createLevelWiseTree(arr):
    root = treeNode(int(arr[0]))
    q = [root]
    size = len(arr)
    i = 1
    while i<size:
        parent = q.pop(0)
        childCount = int(arr[i])
        i += 1
        for j in range(0,childCount):
            temp = treeNode(int(arr[i+j]))
            parent.children.append(temp)
            q.append(temp)
        i += childCount
    return root

# Main
sys.setrecursionlimit(10**6)
arr = list(int(x) for x in input().strip().split(' '))
tree = createLevelWiseTree(arr)
printLevelWiseTree(tree)<jupyter_output><empty_output><jupyter_text>Contains x    Given a generic tree and an integer x, check if x is present in the given tree or not. Return true if x is present, return false otherwise.    Input format :    The first line of input contains data of the nodes of the tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.      The following line contains an integer, that denotes the value of x.    Output format :    The first and only line of output contains true, if x is present and false, otherwise.    Constraints:    Time Limit: 1 sec    Sample Input 1 :    10 3 20 30 40 2 40 50 0 0 0 0    40     Sample Output 1 :    true    Sample Input 2 :    10 3 20 30 40 2 40 50 0 0 0 0    4     Sample Output 2:    false<jupyter_code>from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)
class treeNode:
    def __init__(self, data):
        self.data = data
        self.children = []
    def __str__(self):
        return str(self.data)

def containsX(tree, x):
    #############################
    # PLEASE ADD YOUR CODE HERE #
    #############################
    if tree.data==x:
        return True
   
    for child in tree.children:
        
        ans =containsX(child, x)
        if ans:
            return True
    return False

def createLevelWiseTree(arr):
    root = treeNode(int(arr[0]))
    q = [root]
    size = len(arr)
    i = 1
    while i<size:
        parent = q.pop(0)
        childCount = int(arr[i])
        i += 1
        for j in range(0,childCount):
            temp = treeNode(int(arr[i+j]))
            parent.children.append(temp)
            q.append(temp)
        i += childCount
    return root

# Main

arr = list(int(x) for x in stdin.readline().strip().split())
x=int(stdin.readline().strip())
tree = createLevelWiseTree(arr)

if (containsX(tree,x)):
    print('true')
else:
    print('false')<jupyter_output><empty_output><jupyter_text>Count leaf Nodes    Given a generic tree, count and return the number of leaf nodes present in the given tree.    Input format :    The first line of input contains data of the nodes of the tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.      Output Format :    The first and only line of output prints the count of leaf nodes present in the given tree.    Constraints:    Time Limit: 1 sec    Sample Input 1 :    10 3 20 30 40 2 40 50 0 0 0 0     Sample Output 1 :    4<jupyter_code>import sys
class treeNode:
    def __init__(self, data):
        self.data = data
        self.children = []
    def __str__(self):
        return str(self.data)

def leafNodeCount(root):
    #############################
    # PLEASE ADD YOUR CODE HERE #
    #############################
    count=0
    if root is None:
        return 0
    
    if len(root.children)==0:
        
        return 1
    
    
    for i in root.children:
        # print(i.data)
        count+= leafNodeCount(i) 
    return count 
        

def createLevelWiseTree(arr):
    root = treeNode(int(arr[0]))
    q = [root]
    size = len(arr)
    i = 1
    while i<size:
        parent = q.pop(0)
        childCount = int(arr[i])
        i += 1
        for j in range(0,childCount):
            temp = treeNode(int(arr[i+j]))
            parent.children.append(temp)
            q.append(temp)
        i += childCount
    return root

# Main
sys.setrecursionlimit(10**6)
arr = list(int(x) for x in input().strip().split(' '))
tree = createLevelWiseTree(arr)
print(leafNodeCount(tree))<jupyter_output><empty_output><jupyter_text>Node with maximum child sum    Given a generic tree, find and return the node for which sum of its data and data of all its child nodes is maximum. In the sum, data of the node and data of its immediate child nodes has to be taken.    Input format :    The first line of input contains data of the nodes of the tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.     Output format :    The first and only line of output contains the data of the node with maximum sum, as described in the task.    Constraints:    Time Limit: 1 sec    Sample Input 1 :    5 3 1 2 3 1 15 2 4 5 1 6 0 0 0 0    Sample Output 1 :    1<jupyter_code>from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)
class treeNode:
    def __init__(self, data):
        self.data = data
        self.children = []
    def sum(self):
        ans = self.data
        for child in self.children:
            ans += child.data
        return ans

def maxSumNode(root,resNode=None,maxsum=0):
     
    # Base Case
    if root == None:
        return
 
    # curr contains the sum of the root
    # and its children
    currsum = root.data
 
    # total no of children
    count = len(root.children)
 
    # for every child call recursively
    for i in range(0, count):
        currsum += root.children[i].data
        resNode, maxsum = maxSumNode(root.children[i],
                                     resNode, maxsum)
 
    # if curr is greater than sum,
    # update it
    if currsum > maxsum:
 
        # resultant node
        resNode = root
        maxsum = currsum
     
    return resNode, maxsum

def createLevelWiseTree(arr):
    root = treeNode(int(arr[0]))
    q = [root]
    size = len(arr)
    i = 1
    while i<size:
        parent = q.pop(0)
        childCount = int(arr[i])
        i += 1
        for j in range(0,childCount):
            temp = treeNode(int(arr[i+j]))
            parent.children.append(temp)
            q.append(temp)
        i += childCount
    return root

# Main
arr = list(int(x) for x in stdin.readline().strip().split())
tree = createLevelWiseTree(arr)
temp, tempSum = maxSumNode(tree)
print(temp.data)<jupyter_output><empty_output><jupyter_text>Structurally identical    Given two generic trees, return true if they are structurally identical. Otherwise return false.    Structural Identical    If the two given trees are made of nodes with the same values and the nodes are arranged in the same way, then the trees are called identical.      Input format :    The first line of input contains data of the nodes of the first tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.      The following line of input contains data of the nodes of the second tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.    Output format :    The first and only line of output contains true, if the given trees are structurally identical and false, otherwise.    Constraints:    Time Limit: 1 sec    Sample Input 1 :    10 3 20 30 40 2 40 50 0 0 0 0     10 3 20 30 40 2 40 50 0 0 0 0    Sample Output 1 :    true    Sample Input 2 :    10 3 20 30 40 2 40 50 0 0 0 0     10 3 2 30 40 2 40 50 0 0 0 0    Sample Output 2:    false<jupyter_code>from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)
class treeNode:
    def __init__(self, data):
        self.data = data
        self.children = []

def isIdentical(tree1, tree2):
    #############################
    # PLEASE ADD YOUR CODE HERE #
    #############################
    if tree1 is None and tree2 is None:
        return True
    elif tree1 is None or tree2 is None:
        return False
    
    tree1Len = len(tree1.children)
    tree2Len = len(tree2.children)
    
    if tree1Len!=tree2Len:
        return False
    
    else:
        if tree1.data == tree2.data:
            for i in range(tree1Len):
                isIdentical(tree1.children[i], tree2.children[i])
            else:
            
                return True  
        return False




def createLevelWiseTree(arr):
    root = treeNode(int(arr[0]))
    q = [root]
    size = len(arr)
    i = 1
    while i<size:
        parent = q.pop(0)
        childCount = int(arr[i])
        i += 1
        for j in range(0,childCount):
            temp = treeNode(int(arr[i+j]))
            parent.children.append(temp)
            q.append(temp)
        i += childCount
    return root

# Main
arr1 = list(int(x) for x in stdin.readline().strip().split())
tree1 = createLevelWiseTree(arr1)
arr2 = list(int(x) for x in stdin.readline().strip().split())
tree2 = createLevelWiseTree(arr2)
if isIdentical(tree1, tree2):
    print('true')
else:
    print('false')<jupyter_output><empty_output><jupyter_text>Next larger    Given a generic tree and an integer n. Find and return the node with next larger element in the tree i.e. find a node with value just greater than n.    Note: Return NULL if no node is present with the value greater than n.    Input format :    The first line of input contains data of the nodes of the tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.      The following line contains an integer, that denotes the value of n.    Output format :    The first and only line of output contains data of the node, whose data is just greater than n.    Constraints:    Time Limit: 1 sec    Sample Input 1 :    10 3 20 30 40 2 40 50 0 0 0 0     18    Sample Output 1 :    20    Sample Input 2 :    10 3 20 30 40 2 40 50 0 0 0 0     21    Sample Output 2:    30<jupyter_code>from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)
class treeNode:
    def __init__(self, data):
        self.data = data
        self.children = []

def nextLargest(tree, n):
    #############################
    # PLEASE ADD YOUR CODE HERE #
    #############################
    if tree is None:
        return None
    temroot=None
    if tree.data>n:
        return tree
    
    for i in tree.children:
        temroot=nextLargest(i, n)


    return temroot


def createLevelWiseTree(arr):
    root = treeNode(int(arr[0]))
    q = [root]
    size = len(arr)
    i = 1
    while i<size:
        parent = q.pop(0)
        childCount = int(arr[i])
        i += 1
        for j in range(0,childCount):
            temp = treeNode(int(arr[i+j]))
            parent.children.append(temp)
            q.append(temp)
        i += childCount
    return root

# Main
arr = list(int(x) for x in stdin.readline().strip().split())
n = int(input())
tree = createLevelWiseTree(arr)
if nextLargest(tree, n):
    print(nextLargest(tree, n).data)<jupyter_output><empty_output><jupyter_text>Replace with depth    You are given a generic tree. You have to replace each node with its depth value. You just have to update the data of each node, there is no need to return or print anything.    Input format :    The first line of input contains data of the nodes of the tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.      Output format:    The updated tree is printed level wise. Each level is printed in a new line. Please refer to sample output 1 for more details.     Constraints:    Time Limit: 1 sec    Sample Input 1:    10 3 20 30 40 2 40 50 0 0 0 0     Sample Output 1:    0     1 1 1     2 2<jupyter_code>from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)

class treeNode:
    def __init__(self, data):
        self.data = data
        self.children = []
        


def replacewithDepth(tree,count=0):
    #############################
    # PLEASE ADD YOUR CODE HERE #
    #############################
    if tree is None:
        return
    tree.data = count
    for i in tree.children:
        replacewithDepth(i,count+1)


def createLevelWiseTree(arr):
    root = treeNode(int(arr[0]))
    q = [root]
    size = len(arr)
    i = 1
    while i<size:
        parent = q.pop(0)
        childCount = int(arr[i])
        i += 1
        for j in range(0,childCount):
            temp = treeNode(int(arr[i+j]))
            parent.children.append(temp)
            q.append(temp)
        i += childCount
    return root

def printLevelAtNewLine(tree):
    q = [tree]
    newq = []
    while q:
        parent = q.pop(0)
        print(parent.data, end=' ')
        for child in parent.children:
            newq.append(child)
        if len(q)==0:
            q = newq
            newq = []
            print()  # Move to next Line

# Main
arr = list(int(x) for x in stdin.readline().strip().split())
tree = createLevelWiseTree(arr)
replacewithDepth(tree)
printLevelAtNewLine(tree)<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup