I was asked to solve a binary tree traversal related problem recently where the aim is to find sum of all nodes in a binary tree where node is odd and its uncle is also odd. I came with a solution as below which is O(n) in algorithmic complexity ( 1 time full traversal of the tree ) and auxillary memory usage which is equal to O(h). If and only if the binary tree happends to be BST and height balanced then it can be argued that the auxillary memory complexity will be O(log(n)).
My solution is a variation on the path identification of all root to leaf problem. This problem and its solution can be found here.
https://github.com/anandkulkarnisg/BinaryTree/blob/main/set2/rootleaf.cpp
The solution to the odd node with odd uncle is given here.
https://github.com/anandkulkarnisg/BinaryTree/blob/main/set5/sumodduncle.cpp
The interviewer agreed that the algorithmic complexity is obvious as one traversal is definitely needed and it is O(n). But he argued that the auxiliary memory complexity can be designed much better than O(h) and he did not tell what the approach was. I have been thinking about this for 2 weeks now and haven't got a better solution yet.
I cleared the interview btw and was offered a role that I am considering now, but I still don't know what the better approach to auxiliary memory tuning is here. Can it be O(1) sounds not possible until somehow we keep track at every node only the parent and grandparent which is then O(1).is that possible?
https://github.com/anandkulkarnisg/BinaryTree/blob/main/set5/sumodduncle.cpp In this code module the solution using the below invocation...
long sumAlt=findSumOddUncle(uniqueBstPtr);
Is the O(1) solution because all variables are passed via pointer and only the sum is passed which accumulates the total in recursive calls. Tested and works as expected.