We shall consider rooted (not necessarily binary) trees; for such a tree T we le

Question

We shall consider rooted (not necessarily binary) trees; for such a tree T we let N(T) denote the number of nodes in T, and h(T) denote the height of T.Let Union be a function that as input takes two rooted trees U and V, and as output returns a tree T given as follows:
• if N(U) > N(V ) then T is like U except that its root has V as an extra child;

• otherwise, then T is like V except that its root has U as an extra child.

Consider a tree T that is formed (from one-element trees) by successive applications of Union. Prove that then h(T) log2(N(T)).

Explanation / Answer

******Try this code ******* public class Node { private List children = new ArrayList(); private Node parent = null; private T data = null; public Node(T data) { this.data = data; } public Node(T data, Node parent) { this.data = data; this.parent = parent; } public List getChildren() { return children; } public void setParent(Node parent) { parent.addChild(this); this.parent = parent; } public void addChild(T data) { Node child = new Node(data); child.setParent(this); this.children.add(child); } public void addChild(Node child) { child.setParent(this); this.children.add(child); } public T getData() { return this.data; } public void setData(T data) { this.data = data; } public boolean isRoot() { return (this.parent == null); } public boolean isLeaf() { if(this.children.size() == 0) return true; else return false; } public void removeParent() { this.parent = null; } }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.