Reachability of nodes in a complete binary tree

From: Joe <Joe.Reddington@xxxxxxxxxxxxxx>
Date: Thu, 17 Jan 2008 08:16:19 -0800 (PST)

I have a complete binary tree of n levels. and 2^n - 1 nodes. Child
nodes are reached from parent nodes by either following a left link or
a right link.

Clearly every node in the tree can be identified by the sequence of
left and right links used to reach it from the root of the tree.

I am interested in the total number of nodes in the tree that can be
reached using only L left links.

I believe the total number of nodes to be less than or equal to
(n-1)^L but I am interested in any proofs or more exact numbers.

Can anyone point me in a sensible direction?

Joe
.

Follow-Ups:
- Re: Reachability of nodes in a complete binary tree
  - From: Mariano Suárez-Alvarez

Prev by Date: Re: Submanifold
Next by Date: Re: divergent series
Previous by thread: For any set E in R, How to prove m* ( E ) = m*_J ( E ) ?
Next by thread: Re: Reachability of nodes in a complete binary tree
Index(es):
- Date
- Thread

Relevant Pages

Re: How to populate a treeview from a dataset
... If it is then check to see if the parentId and child id of the ... 15 is a parent and a child of itself. ... And that same business is the headquarters for the purchasing group. ... 15 Null - root tree node, ...
(microsoft.public.dotnet.languages.csharp)
Re: How to populate a treeview from a dataset
... If it is then check to see if the parentId and child id of the ... 15 is a parent and a child of itself. ... And that same business is the headquarters for the purchasing group. ... 15 Null - root tree node, ...
(microsoft.public.dotnet.languages.csharp)
Re: CPropertySheet - dynamic pages in wizard mode
... Another method that I considered using was a Tree or List / splitter / child ... 'Tabs' to show however decided against it as while it would have been ... Wizard does the Create of the xxx ojbect type. ...
(microsoft.public.vc.mfc)
RE: Adding Child Nodes to Treeview
... you can determine if the current node number is odd ... So to get to the "parent" node (child of human/animal parent) you would use ... This is considered a binary tree. ...
(microsoft.public.access.modulesdaovba)
Windows 2003 SP1 Replication Issue
... tree, but the root tree can't pull from the child tree. ... When a workstation / user in the parent domain connects to the server in ...
(microsoft.public.windows.server.active_directory)