Have the function TreeConstructor(strArr) take the array of strings stored in strArr, which will contain pairs of integers in the following format: (i1,i2), where i1 represents a child node in a tree and the second integer i2 signifies that it is the parent of i1. For example: if strArr is [“(1,2)”, “(2,4)”, “(7,2)”], then this forms the following tree:
4 / 2 / \ 1 7which you can see forms a proper binary tree. Your program should, in this case, return the string true because a valid binary tree can be formed. If a proper binary tree cannot be formed with the integer pairs, then return the string false. All of the integers within the tree will be unique, which means there can only be one node in the tree with the given integer value.
Examples
Input: [“(1,2)”, “(2,4)”, “(5,7)”, “(7,2)”, “(9,5)”]
Output: trueInput: [“(1,2)”, “(3,2)”, “(2,12)”, “(5,2)”]
Output: falseTags
array binary treedata engineer Google Facebook
Tree Constructor Algorithms using Hash Table
A valid tree should have the following characteristics:
- A node should have at most 1 parent – the root does not have parents.
- A node should have at most 2 children.
So, we can use two hash tables to record the number of parents and children for each node and return False immediately when we found violations.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def TreeConstructor(strArr): parents = {} children = {} for s in strArr: a, b = map(int, s.replace('(', '').replace(')', '').split(',')) if a in parents: return False else: parents[a] = True if b in children: children[b] += 1 if children[b] > 2: return False else: children[b] = 1 return True |
def TreeConstructor(strArr): parents = {} children = {} for s in strArr: a, b = map(int, s.replace('(', '').replace(')', '').split(',')) if a in parents: return False else: parents[a] = True if b in children: children[b] += 1 if children[b] > 2: return False else: children[b] = 1 return True
The space complexity is O(N) and the time complexity is also O(N).
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Big O Simply Explained
Next Post: How to Re-mount a RAID-1 Array into a RAID-0 on Linux VPS?
It gives wrong output for the example [(1,2), (2,5),(3,2), (4,2)]
where the tree forms a cycle.