0
votes
0answers
61 views

Structural induction on internal nodes of a binary tree

I know my language is not super mathematic, but I want to make sure I have the logic down. Here is my proof for the number of internal nodes in a binary tree being equal to the floor_function(n/2), ...
0
votes
1answer
244 views

Number of nodes in binary tree given number of leaves

How would I prove that any binary tree that has n leaves has precisely $2n-1$ nodes ? Given that a binary tree is either a single node "o" or a node with the left and right subtrees contains a binary ...
0
votes
2answers
103 views

Use strong induction to prove number of vertices on complete tree is $2l-1$

Can someone help me construct this proof using strong induction? Use strong induction on $l$ to show that for all $l \geq 1$, a full binary tree with $l$ leaves has $2l-1$ vertices total.
0
votes
0answers
99 views

max number of keys in a 2-3-4 tree

Let $M(L)$ be the largest number of keys (a $2$-node has $1$ key and two children, a $3$-node has $2$ keys and $3$ children, and a $4$-node has $3$ keys and $4$ children) in a $2-3-4$ tree that ...
0
votes
1answer
174 views

Let T be a tree with sub-trees which each set has a vertex in common - hence T has a vertex in all of its sub-trees?

The question is: Let T be a tree with sub-trees $T_1,T_2,..,T_n$ such that all trees $T_i,T_j$ have a vertex in common which each set has a vertex in common - show that T has a vertex in all $T_i$. ...
2
votes
2answers
1k views

Proof by induction and height of a binary tree

I need some help with a simple proof. I want to know if this proof is correct: Let's define the height of a binary tree node as: 0, if the node is a leaf 1 + the maximum height of the children ...
0
votes
1answer
349 views

Proving by induction

I'm having a problem relating to proving by induction that the Preorder(T) and Postorder(T) algorithms both print out all the nodes in the tree without repetition. I'm not quite sure where to start.. ...
1
vote
3answers
1k views

Sufficient conditions on degrees of vertices for existence of a tree

I am answering a question for an assignment, but I am not sure if my proof is valid, can someone look at it for me? the question: "there is a tree with $p$ vertices. If $d_1, d_2, \dots , d_p$ are ...