edu.stanford.math.plex4.graph.random

Class BinaryTree

java.lang.Object

edu.stanford.math.plex4.graph.random.BinaryTree

public class BinaryTree
extends java.lang.Object

Implements a binary tree of nodes labeled 1,2,...,n.

Author:

Tim Harrington

Field Summary

Fields

Modifier and Type	Field and Description
protected int	n

Constructor Summary

Constructors

Constructor and Description
BinaryTree(int n)

Method Summary

Methods

Modifier and Type	Method and Description
int	commonAncestorDepth(int i, int j)
int	getCommonAncestor(int i, int j)
int	getDepth(int i) Returns the depth of a node in a breadth-first labeled binary tree rooted at 1.
int	getMaxDepth()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

n

protected int n

Constructor Detail

BinaryTree

public BinaryTree(int n)

Method Detail

getMaxDepth

public int getMaxDepth()

Returns:

the depth of the deepest node in the tree

getDepth

public int getDepth(int i)

Returns the depth of a node in a breadth-first labeled binary tree rooted at 1. The depth of node 1 is 0.

Parameters:

i - node label

Returns:

the depth of node i in the tree

getCommonAncestor

public int getCommonAncestor(int i,
                    int j)

Parameters:

i - node label

j - node label

Returns:

the label of the first common ancestor in the tree

commonAncestorDepth

public int commonAncestorDepth(int i,
                      int j)

Parameters:

i - node label

j - node label

Returns:

tree depth of the first common ancestor of i and j