Python program to find root of the tree where children id sum for every node is given.














































Python program to find root of the tree where children id sum for every node is given.



Description:
Consider here a binary tree  whose nodes have ids from 1 to n where n is the number of nodes in the tree. The tree is given as a collection of n pairs, where every pair represents node id and sum of children ids.

So the idea is that every node id appears in children sum except root. So if we do sum of all ids and subtract it from sum of all children sums, we get root.

Program:

'''Find root of tree where children sum for every node id is given''' def findRoot(arr, n) : root = 0 # Every node appears once as an id, and # every node except for the root appears # once in a sum. So if we subtract all # the sums from all the ids, we%u2019re left # with the root id. for i in range(n): root += (arr[i][0]-arr[i][1]) return root # Driver Code if __name__ == '__main__': arr = [[1, 5], [2, 0], [3, 0], [4, 0], [5, 5], [6, 5]] n = len(arr) print(findRoot(arr, n))

Output:
6
>>>

More Articles of Khushboo Singh:

Name Views Likes
Python program to insert an element in binary tree. 887 20
Tokenize text using NLTK in Python. 1266 12
Python Remove multiple elements from list while Iterating. 793 22
Python How to Check if an item exists in list ? 4343 14
Python How to remove multiple elements from list ? 814 26
Python program to check if two trees are mirror of each other without using recursion. 713 19
Python program to find maximum in Binary tree. 998 19
Python Check if all elements are same using Set 771 15
Python program to find diameter of a binary tree. 1139 20
Python program to print root to leaf paths without using recursion. 885 20
Python program to find root of the tree where children id sum for every node is given. 725 23
Introduction of Python NLTK library 1420 25
Categorizing and Tagging Sentences using NLTK in Python . 1081 19
Python program to find height of a tree without using recursion. 710 16
Python program to find sum of all nodes of the given perfect binary tree. 713 19
Python program to find minimum in binary tree. 876 23
Python Check if element exist in list using list.count() function. 735 13
Python program to convert a given binary tree to doubly linked list. 940 20
Python program to find distance between two nodes of a binary tree. 1575 20
NLTK stop Words 1228 13
Python program to find largest binary search tree in a Binary Tree. 987 20
Python program to find inorder successor in binary search tree with recursion. 1258 18
Python program to convert a binary tree into doubly linked list in spiral fashion. 848 15
Python List check if element are same using all() 724 12
Python program to check if two trees are identical using recursion. 752 30
Python Find the occurrence count of an element in the tuple using count() 1014 23
Python Convert two lists to a dictionary 781 19
Python program to construct a complete binary tree from given array. 1496 14
Python program to find diameter of binary tree in O(n). 924 17
Introduction to the AVL tree. 825 15
Python program to check if two trees are identical without using recursion 710 17
Python Convert a list of tuples to dictionary. 1151 24
Python program to convert a binary tree to a circular doubly link list. 698 21
Python Check if element exist in list based on own logic. 804 23
Python program to merge two binary trees by doing node sum using recursion 1060 27
Python program to check whether a given binary tree is perfect or not. 735 17
Python Check if all elements are same using list.count(). 1156 28
Python program to find an element into binary tree 670 12
Python program to find lowest common ancestor in a binary tree 1267 24

Comments