In a tree, a sibling is any node that shares its parent with another node. Prove
ID: 3663571 • Letter: I
Question
In a tree, a sibling is any node that shares its parent with another node. Prove by induction that the number of leaves L in a binary tree T and the number of siblings S in the tree obey the following relationship, provided there is at least one node in the tree: L = (S + 2)/2 Basis. Show that the relationship holds in the case of a one-node tree. Introduction Hypothesis. We will do introduction over the number of nodes in the tree. What is the introduction hypothesis? Introduction Step. Show that if the relationship is true for any tree with n nodes, then it is also true for any tree with n +1 nodes. There are two cases, depending on whether the new node is a sibling or not. Conclusion. What is the conclusion?Explanation / Answer
Siblings mean all nodes at the same level .
we know a binary tree consists of two nodes connecting to a node so there may be multiples of two siblings(max case) and odd number for least case.
let for suppose we have 3 nodes and the tree structure would be 1 here 4 n 5 are the child/leaf and also sibling
/
4 5
equation to find the no of siblings is 3+1/2==2
therefore the equation is true
a level order traversal of the tree and visiting each node once, so the time complexity is O(n). We are using a queue to maintain a list of nodes pending to be traversed. At any given point, the max length of the queue would be a number of nodes at a given level. For a complete binary tree (worst-case-analysis), this would ne n/2 for the last level. So the worst case space complexity is O(n).
the way to find siblings using code is as follows
public void FindSiblings(TreeNode node)
{
Queue<TreeNode> q = new Queue<TreeNode>();
q.Enqueue(node);
TreeNode previous = null;
TreeNode current = null;
while (q.Count > 0)
{
current = q.Dequeue();
if (current.Left != null)
{
q.Enqueue(current.Left);
}
if (current.Right != null)
{
q.Enqueue(current.Right);
}
if (previous != null && previous.Data < current.Data)
{
previous.Sibling = current;
Console.WriteLine(previous.Data + " : " + previous.Sibling.Data);
}
previous = current;
}
}
every node within the binary tree will have a relation ship between each other so only the case sibling or not .
but as every node having relation with each other the above level node becomes the parent and the nodes in one layer becomes siblings no matter that node should have same parent to become a sibling.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.