Implementation:Interpretml Interpret TreeNode

Knowledge Sources	Interpretml Interpret
Domains	Machine_Learning, EBM_Core
Last Updated	2026-02-07 12:00 GMT

Overview

TreeNode is a C++ header module that defines the tree node data structure used for building 1-dimensional decision trees during EBM boosting.

Description

The TreeNode struct is a POD (Plain Old Data) type that represents a single node in a binary decision tree built during 1-dimensional boosting. It uses a union-based state machine design that tracks the node through its lifecycle stages: initialization, gain calculation, queuing, splitting, and deconstruction.

Key design features:

• Union-based state machine: The node uses a C++ union (TreeNodeUnion) with three states:
  • BeforeGainCalc: Stores a pointer to the first bin in the node's range
  • AfterGainCalc: Stores the split gain value
  • Deconstruct: Stores a parent pointer for tree traversal during tensor construction

• Shared pointer (pPointerBinLastOrChildren): A multi-purpose void* pointer that stores either:
  • The last bin pointer (before gain calculation)
  • Child node pointer (after split)
  • Null marker (after right child traversal during deconstruction)

• Debug stage tracking: In debug builds, an enum tracks the progression through lifecycle stages (Initialized, SetFirstOrLastBin, SetFirstAndLastBin, QueuingRejected, Queued, Split, DestructTraversedLeft, DestructTraversedRight, DONE) with assertions at each transition.

• Embedded Bin: Each node contains a Bin at the end of the struct (using the struct hack for variable-length scoring) that stores the cumulative sample count, weight, gradient sum, and hessian sum for the node.

The header also provides utility functions: IsOverflowTreeNodeSize, GetTreeNodeSize, IndexTreeNode, GetLeftNode, and GetRightNode.

Usage

TreeNodes are used during the 1-dimensional boosting phase when building decision trees for individual features. Nodes are allocated in contiguous memory blocks and managed via pointer arithmetic rather than dynamic allocation.

Code Reference

Source Location

• Repository: Interpretml_Interpret
• File: shared/libebm/TreeNode.hpp

Signature

template<bool bHessian, size_t cCompilerScores = 1>
struct TreeNode final {
    inline void Init();

    // Before gain calculation
    inline void BEFORE_SetBinFirst(const Bin<...>* const* const pBinFirst);
    inline void BEFORE_SetBinLast(const Bin<...>* const* const pBinLast);
    inline const Bin<...>* const* BEFORE_GetBinFirst() const;
    inline const Bin<...>* const* BEFORE_GetBinLast() const;

    // After gain calculation
    inline void AFTER_RejectSplit();
    inline void AFTER_SetSplitGain(const FloatMain splitGain, TreeNode* const pChildren);
    inline FloatMain AFTER_GetSplitGain() const;
    inline TreeNode* AFTER_GetChildren();
    inline bool AFTER_IsSplit() const;
    inline bool AFTER_IsSplittable() const;
    inline void AFTER_SplitNode();

    // Deconstruction traversal
    inline TreeNode* DECONSTRUCT_TraverseLeftAndMark(TreeNode* const pParent);
    inline bool DECONSTRUCT_IsRightChildTraversal();
    inline TreeNode* DECONSTRUCT_TraverseRightAndMark(const size_t cBytesPerTreeNode);
    inline TreeNode* DECONSTRUCT_GetParent();

    // Bin access
    inline Bin<...>* GetBin();
    inline const Bin<...>* GetBin() const;
};

inline static bool IsOverflowTreeNodeSize(const bool bHessian, const size_t cScores);
inline static size_t GetTreeNodeSize(const bool bHessian, const size_t cScores);

I/O Contract

Inputs

Name	Type	Required	Description
bHessian	bool (template)	Yes	Whether hessian information is tracked in the node
cCompilerScores	size_t (template)	No	Compile-time score count (default 1, or k_dynamicScores)

Outputs

Name	Type	Description
TreeNode instance	struct	A tree node containing bin statistics and split information

Usage Examples

Pipeline Context

# This C++ module is called internally via the native bindings
# during 1-dimensional boosting tree construction
from interpret.glassbox import ExplainableBoostingClassifier
ebm = ExplainableBoostingClassifier()
ebm.fit(X, y)  # Internally uses TreeNode for building per-feature trees

Related Pages

• Environment:Interpretml_Interpret_Native_Libebm_Environment