goog.structs.TreeNode

Provided By	`goog.structs.TreeNode`
Extends	`goog.structs.Node<KEY, VALUE>`

Generic tree node data structure with arbitrary number of child nodes. It is possible to create a dynamic tree structure by overriding #getParent and #getChildren in a subclass. All other getters will automatically work.

new TreeNode`<KEY, VALUE>`( `key`, `value` )

Parameters

`key`	`(KEY\|null)`
	Key.
`value`	`(VALUE\|null)`
	Value.

VIEW SOURCE

Instance Methods

Appends a child node to this node.

Overrides

goog.structs.TreeNode

Parameters

`child`	`goog.structs.TreeNode<(KEY\|null), (VALUE\|null)>`
	Orphan child node.

VIEW SOURCE

Inserts a child node at the given index.

Overrides

goog.structs.TreeNode

Parameters

`child`	`goog.structs.TreeNode<(KEY\|null), (VALUE\|null)>`
	Orphan child node.
`index`	`number`
	The position to insert at.

VIEW SOURCE

Clones a node and returns a new node.

Overrides

goog.structs.TreeNode

Parameters

None.

Returns

goog.structs.TreeNode

Clone of the tree node without its parent and child nodes. The key and the value are copied by reference.

VIEW SOURCE

Tells whether this node is the ancestor of the given node.

Overrides

goog.structs.TreeNode

Parameters

`node`	`goog.structs.TreeNode<(KEY\|null), (VALUE\|null)>`
	A node.

Returns

boolean

Whether this node is the ancestor of node.

VIEW SOURCE

Overrides

goog.structs.TreeNode

Parameters

None.

Returns

goog.structs.TreeNode

Clone of the subtree with this node as root.

VIEW SOURCE

Traverses all child nodes.

Overrides

goog.structs.TreeNode

Parameters

`f`	`function(goog.structs.TreeNode<(KEY\|null), (VALUE\|null)>, number, Array<goog.structs.TreeNode<(KEY\|null), (VALUE\|null)>>): ?`
	Callback function. It takes the node, its index and the array of all child nodes as arguments.
`opt_this`	`(THIS\|null)=`
	The object to be used as the value of `this` within `f`.

VIEW SOURCE

Traverses all child nodes recursively in preorder.

Overrides

goog.structs.TreeNode

Parameters

`f`	`function(goog.structs.TreeNode<(KEY\|null), (VALUE\|null)>): ?`
	Callback function. It takes the node as argument.
`opt_this`	`(THIS\|null)=`
	The object to be used as the value of `this` within `f`.

VIEW SOURCE

Overrides

goog.structs.TreeNode

Parameters

None.

Returns

Array<goog.structs.TreeNode<(KEY|null), (VALUE|null)>>

All ancestor nodes in bottom-up order.

VIEW SOURCE

Gets the child node of this node at the given index.

Overrides

goog.structs.TreeNode

Parameters

`index`	`number`
	Child index.

Returns

(goog.structs.TreeNode<KEY, VALUE>|null)

The node at the given index or null if not found.

VIEW SOURCE

Overrides

goog.structs.TreeNode

Parameters

None.

Returns

number

The number of children.

VIEW SOURCE

Overrides

goog.structs.TreeNode

Parameters

None.

Returns

Array<goog.structs.TreeNode<(KEY|null), (VALUE|null)>>

Immutable child nodes.

VIEW SOURCE

Overrides

goog.structs.TreeNode

Parameters

None.

Returns

number

The number of ancestors of the node.

VIEW SOURCE

Gets the key.

Defined by

goog.structs.Node

Parameters

None.

Returns

KEY

The key.

VIEW SOURCE

Returns a node whose key matches the given one in the hierarchy rooted at this node. The hierarchy is searched using an in-order traversal.

Overrides

goog.structs.TreeNode

Parameters

`key`	`(KEY\|null)`
	The key to search for.

Returns

(goog.structs.TreeNode<KEY, VALUE>|null)

The node with the given key, or null if no node with the given key exists in the hierarchy.

VIEW SOURCE

Overrides

goog.structs.TreeNode

Parameters

None.

Returns

(goog.structs.TreeNode<KEY, VALUE>|null)

Parent node or null if it has no parent.

VIEW SOURCE

Overrides

goog.structs.TreeNode

Parameters

None.

Returns

goog.structs.TreeNode<(KEY|null), (VALUE|null)>

The root of the tree structure, i.e. the farthest ancestor of the node or the node itself if it has no parents.

VIEW SOURCE

Builds a nested array structure from the node keys in this node's subtree to facilitate testing tree operations that change the hierarchy.

Overrides

goog.structs.TreeNode

Parameters

None.

Returns

Array<(KEY|null)>

The structure of this node's descendants as nested array of node keys. The number of unclosed opening brackets up to a particular node is proportional to the indentation of that node in the graphical representation of the tree. Example:

this
|- child1
|  L- grandchild
L- child2

is represented as ['child1', ['grandchild'], 'child2'].

VIEW SOURCE

Gets the value.

Defined by

goog.structs.Node

Parameters

None.

Returns

VALUE

The value.

VIEW SOURCE

Tells if the node is the last child of its parent. This method helps how to connect the tree nodes with lines: L shapes should be used before the last children and |- shapes before the rest. Schematic tree visualization:

 Node1
 |-Node2
 | L-Node3
 |   |-Node4
 |   L-Node5
 L-Node6

Overrides

goog.structs.TreeNode

Parameters

None.

Returns

boolean

Whether the node has parent and is the last child of it.

VIEW SOURCE

Overrides

goog.structs.TreeNode

Parameters

None.

Returns

boolean

Whether the node is a leaf node.

VIEW SOURCE

Removes the given child node of this node.

Overrides

goog.structs.TreeNode

Parameters

`child`	`(goog.structs.TreeNode<(KEY\|null), (VALUE\|null)>\|null)`
	The node to remove.

Returns

(goog.structs.TreeNode<KEY, VALUE>|null)

The removed node if any.

VIEW SOURCE

Removes the child node at the given index.

Overrides

goog.structs.TreeNode

Parameters

`index`	`number`
	The position to remove from.

Returns

(goog.structs.TreeNode<KEY, VALUE>|null)

The removed node if any.

VIEW SOURCE

Removes all child nodes of this node.

Overrides	`goog.structs.TreeNode`
Parameters	None.

VIEW SOURCE

Replaces the given child node.

Overrides

goog.structs.TreeNode

Parameters

`newChild`	`goog.structs.TreeNode<(KEY\|null), (VALUE\|null)>`
	New node to replace `oldChild`. It must not have parent node.
`oldChild`	`goog.structs.TreeNode<(KEY\|null), (VALUE\|null)>`
	Existing child node to be replaced.

Returns

goog.structs.TreeNode<(KEY|null), (VALUE|null)>

The replaced child node detached from its parent.

VIEW SOURCE

Replaces a child node at the given index.

Overrides

goog.structs.TreeNode

Parameters

`newChild`	`goog.structs.TreeNode<(KEY\|null), (VALUE\|null)>`
	Child node to set. It must not have parent node.
`index`	`number`
	Valid index of the old child to replace.

Returns

goog.structs.TreeNode<(KEY|null), (VALUE|null)>

The original child node, detached from its parent.

VIEW SOURCE

Sets the parent node of this node. The callers must ensure that the parent node and only that has this node among its children.

Overrides

goog.structs.TreeNode

Parameters

`parent`	`(goog.structs.TreeNode<(KEY\|null), (VALUE\|null)>\|null)`
	The parent to set. If null, the node will be detached from the tree.

VIEW SOURCE

Traverses the subtree with the possibility to skip branches. Starts with this node, and visits the descendant nodes depth-first, in preorder.

Overrides

goog.structs.TreeNode

Parameters

`f`	`function(goog.structs.TreeNode<(KEY\|null), (VALUE\|null)>): (boolean\|undefined)`
	Callback function. It takes the node as argument. The children of this node will be visited if the callback returns true or undefined, and will be skipped if the callback returns false.
`opt_this`	`(THIS\|null)=`
	The object to be used as the value of `this` within `f`.

VIEW SOURCE

Static Functions

Finds the deepest common ancestor of the given nodes. The concept of ancestor is not strict in this case, it includes the node itself.

Parameters

`var_args`	`...goog.structs.TreeNode<(KEY\|null), (VALUE\|null)>`
	The nodes.

Returns

(goog.structs.TreeNode<KEY, VALUE>|null)

The common ancestor of the nodes or null if they are from different trees.

VIEW SOURCE

goog.structs.TreeNode`<KEY, VALUE>`

new TreeNode`<KEY, VALUE>`( `key`, `value` )

Instance Methods

`this.`addChild( `child` ) `→` `void`

`this.`addChildAt( `child`, `index` ) `→` `void`

`this.`clone() `→` `goog.structs.TreeNode`

`this.`contains( `node` ) `→` `boolean`

`this.`deepClone() `→` `goog.structs.TreeNode`

`this.`forEachChild`<THIS>`( `f`, `opt_this` ) `→` `void`

`this.`forEachDescendant`<THIS>`( `f`, `opt_this` ) `→` `void`

`this.`getAncestors() `→` `Array<goog.structs.TreeNode<(KEY|null), (VALUE|null)>>`

`this.`getChildAt( `index` ) `→` `(goog.structs.TreeNode<KEY, VALUE>|null)`

`this.`getChildCount() `→` `number`

`this.`getChildren() `→` `Array<goog.structs.TreeNode<(KEY|null), (VALUE|null)>>`

`this.`getDepth() `→` `number`

`this.`getKey() `→` `KEY`

`this.`getNodeByKey( `key` ) `→` `(goog.structs.TreeNode<KEY, VALUE>|null)`

`this.`getParent() `→` `(goog.structs.TreeNode<KEY, VALUE>|null)`

`this.`getRoot() `→` `goog.structs.TreeNode<(KEY|null), (VALUE|null)>`

`this.`getSubtreeKeys() `→` `Array<(KEY|null)>`

`this.`getValue() `→` `VALUE`

`this.`isLastChild() `→` `boolean`

`this.`isLeaf() `→` `boolean`

`this.`removeChild( `child` ) `→` `(goog.structs.TreeNode<KEY, VALUE>|null)`

`this.`removeChildAt( `index` ) `→` `(goog.structs.TreeNode<KEY, VALUE>|null)`

`this.`removeChildren() `→` `void`

`this.`replaceChild( `newChild`, `oldChild` ) `→` `goog.structs.TreeNode<(KEY|null), (VALUE|null)>`

`this.`replaceChildAt( `newChild`, `index` ) `→` `goog.structs.TreeNode<(KEY|null), (VALUE|null)>`

`this.`setParent( `parent` ) `→` `void`

`this.`traverse`<THIS>`( `f`, `opt_this` ) `→` `void`

Static Functions

TreeNode.findCommonAncestor`<KEY, VALUE>`( `...var_args` ) `→` `(goog.structs.TreeNode<KEY, VALUE>|null)`

goog.structs.TreeNode<KEY, VALUE>

new TreeNode<KEY, VALUE>( key, value )

Instance Methods

this.addChild( child ) → void

this.addChildAt( child, index ) → void

this.clone() → goog.structs.TreeNode

this.contains( node ) → boolean

this.deepClone() → goog.structs.TreeNode

this.forEachChild<THIS>( f, opt_this ) → void

this.forEachDescendant<THIS>( f, opt_this ) → void

this.getAncestors() → Array<goog.structs.TreeNode<(KEY|null), (VALUE|null)>>

this.getChildAt( index ) → (goog.structs.TreeNode<KEY, VALUE>|null)

this.getChildCount() → number

this.getChildren() → Array<goog.structs.TreeNode<(KEY|null), (VALUE|null)>>

this.getDepth() → number

this.getKey() → KEY

this.getNodeByKey( key ) → (goog.structs.TreeNode<KEY, VALUE>|null)

this.getParent() → (goog.structs.TreeNode<KEY, VALUE>|null)

this.getRoot() → goog.structs.TreeNode<(KEY|null), (VALUE|null)>

this.getSubtreeKeys() → Array<(KEY|null)>

this.getValue() → VALUE

this.isLastChild() → boolean

this.isLeaf() → boolean

this.removeChild( child ) → (goog.structs.TreeNode<KEY, VALUE>|null)

this.removeChildAt( index ) → (goog.structs.TreeNode<KEY, VALUE>|null)

this.removeChildren() → void

this.replaceChild( newChild, oldChild ) → goog.structs.TreeNode<(KEY|null), (VALUE|null)>

this.replaceChildAt( newChild, index ) → goog.structs.TreeNode<(KEY|null), (VALUE|null)>

this.setParent( parent ) → void

this.traverse<THIS>( f, opt_this ) → void

Static Functions

TreeNode.findCommonAncestor<KEY, VALUE>( ...var_args ) → (goog.structs.TreeNode<KEY, VALUE>|null)

goog.structs.TreeNode`<KEY, VALUE>`

new TreeNode`<KEY, VALUE>`( `key`, `value` )

`this.`addChild( `child` ) `→` `void`

`this.`addChildAt( `child`, `index` ) `→` `void`

`this.`clone() `→` `goog.structs.TreeNode`

`this.`contains( `node` ) `→` `boolean`

`this.`deepClone() `→` `goog.structs.TreeNode`

`this.`forEachChild`<THIS>`( `f`, `opt_this` ) `→` `void`

`this.`forEachDescendant`<THIS>`( `f`, `opt_this` ) `→` `void`

`this.`getAncestors() `→` `Array<goog.structs.TreeNode<(KEY|null), (VALUE|null)>>`

`this.`getChildAt( `index` ) `→` `(goog.structs.TreeNode<KEY, VALUE>|null)`

`this.`getChildCount() `→` `number`

`this.`getChildren() `→` `Array<goog.structs.TreeNode<(KEY|null), (VALUE|null)>>`

`this.`getDepth() `→` `number`

`this.`getKey() `→` `KEY`

`this.`getNodeByKey( `key` ) `→` `(goog.structs.TreeNode<KEY, VALUE>|null)`

`this.`getParent() `→` `(goog.structs.TreeNode<KEY, VALUE>|null)`

`this.`getRoot() `→` `goog.structs.TreeNode<(KEY|null), (VALUE|null)>`

`this.`getSubtreeKeys() `→` `Array<(KEY|null)>`

`this.`getValue() `→` `VALUE`

`this.`isLastChild() `→` `boolean`

`this.`isLeaf() `→` `boolean`

`this.`removeChild( `child` ) `→` `(goog.structs.TreeNode<KEY, VALUE>|null)`

`this.`removeChildAt( `index` ) `→` `(goog.structs.TreeNode<KEY, VALUE>|null)`

`this.`removeChildren() `→` `void`

`this.`replaceChild( `newChild`, `oldChild` ) `→` `goog.structs.TreeNode<(KEY|null), (VALUE|null)>`

`this.`replaceChildAt( `newChild`, `index` ) `→` `goog.structs.TreeNode<(KEY|null), (VALUE|null)>`

`this.`setParent( `parent` ) `→` `void`

`this.`traverse`<THIS>`( `f`, `opt_this` ) `→` `void`

TreeNode.findCommonAncestor`<KEY, VALUE>`( `...var_args` ) `→` `(goog.structs.TreeNode<KEY, VALUE>|null)`