Locking in a tree
A binary tree node can be locked or unlocked only if none of its parents or children are locked. Assume each node has parent pointer. Write the following methods -
- to test if a node is locked
- to lock a given node, should return if we were able to lock else false
- to unloack a given node,
Solution
- For each node keep track of the number of nodes in its subtree that are locked
- To lock,
- check child locked count
- check all nodes in the path to parent
- if none of the above are locked, then mark node as locked
- To unlock
- mark node as unlocked
- update all nodes in the path to parent and decrement their lock count
Code
class BinaryTreeNode
attr_accessor :is_locked, :lock_count, :parent
def is_locked?
return @is_locked
end
def lock
return false if @lock_count != 0
# Check all nodes on path to parents if they are locked
iter = @parent
while iter
return false if iter.is_locked?
iter = iter-> parent
end
@is_locked = true
# Update lock count for all nodes on path to parent
iter = @parent
while iter
iter.lock_count += 1
iter = iter.parent
end
return true
end
def unlock
return if is_locked == false
@is_locked = false
# Update all nodes on path to parent
iter = @parent
while iter
iter.lock_count -= 1
iter = iter.parent
end
end
end