# Tagged Questions

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), ...
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 ...
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.
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 ...
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$. ...
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 ...
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.. ...
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 ...