Re: Binary Tree Depth()

Stephen Howe wrote:

I dont see that.
Unless you had absolute height stored at the node.
In that case it is O(1) as you examine the root.

But suppose instead it is relative
And say for the sake of argument you have +1, 0 or -1 stored at the node indicating which side of the tree is heavier. It is all relative.
and lets say the root is 0. If you examine the root's left child, it indicates -1, if you examine the root's right child it indicates +1
Now what?

The depth is the maximum depth of all branches. So, iterate starting from the root node: (0 means equal, -1 right is deeper, +1 left):

depth=0
n=root
while (!leaf(n))
depth=depth+1
if (balance(n)=-1)
n=right(n)
else
n=left(n)
end
end

This is an O(log N) algorithm

Christian
.

Relevant Pages

  • Re: Binary Tree Depth()
    ... current depth exceeds maximum depth, ... In that case it is Oas you examine the root. ... If you examine the root's left child, ... It really depends on the rules governing the binary tree. ...
    (comp.programming)
  • Re: Domain Security Problem - Please advise
    ... The child domain DC's always logon as domain admins, while the root DC's always logon as Enterprise Admins. ... We even use MOM to monitor the domain, and this has not picked up any forest wide replication problems, but whatever has happened, the problem is there. ... We have a separate forest root, with child sub-domains which the users log into. ...
    (microsoft.public.windows.server.security)
  • Re: DNS Restructure
    ... What I mean by child root is we have a regional ... It's my understanding that if each internal DNS server is using ... >> external DNS servers are separate and we host both. ...
    (microsoft.public.windows.server.dns)
  • Re: Domain Security Problem - Please advise
    ... Fair point about the permissions being use in replmon, ... DCOM is configured and working on the child and root DC's, but I've reset the DCOM security on this anyway using 'certutil -setreg SetupStatus -SETUP_DCOM_SECURITY_UPDATED_FLAG' then stopping and restarting certsvc on both the root and subordinate CA's. ... This 'setup' has allowed replication and CA config to work without a problem for a long time. ...
    (microsoft.public.windows.server.security)
  • Re: Do Child DCs need unrestricted IP access to Root DCs?
    ... Do all child DC's need unrestricted IP access to all root DC's for AD ... replication to work successfully? ... Site1 can't talk to site3. ...
    (microsoft.public.windows.server.active_directory)
Loading